#1169760 (C++23) No.399 動的な領主

• 問題: No.399 動的な領主
• ユーザー: iastm
• 提出日時: 2026-06-28 08:43:50
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 376 ms / 2,000 ms
• コード長: 7,893 bytes
• コンパイル時間: 2,022 ms
• コンパイル使用メモリ: 170,020 KB
• 実行使用メモリ: 6,528 KB
• 最終ジャッジ日時: 2026-06-28 08:44:48
• 合計ジャッジ時間: 11,442 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_1

ファイルパターン	結果
other	AC * 19

ソースコード

#include <iostream>
#include <vector>
// #include <kotone/link_cut_tree>
// https://github.com/amiast/cpp-utility

#ifndef KOTONE_LINK_CUT_TREE_HPP
#define KOTONE_LINK_CUT_TREE_HPP 1

#include <vector>
#include <cassert>

namespace kotone {

// A data structure for maintaining path aggregation in a forest.
// Optionally, provide the following functions to enable aggregation queries:
// - `void on_update(int parent, int left, int right)`
// - `void on_reverse(int parent, int left, int right)`
// - `void on_push(int parent, int left, int right)`
//
// Reference: https://usaco.guide/adv/link-cut-tree
template <
    void (*on_update)(int, int, int) = nullptr,
    void (*on_reverse)(int, int, int) = nullptr,
    void (*on_push)(int, int, int) = nullptr
> struct link_cut_tree {
    struct splay_vertex {
        int parent = -1, left = -1, right = -1, size = 1;
        bool rev = false;
    };
    std::vector<splay_vertex> _vec;
    int _len = 0;

    void _update(int v) {
        int l = _vec[v].left, r = _vec[v].right;
        _vec[v].size = 1;
        if (l != -1) _vec[v].size += _vec[l].size;
        if (r != -1) _vec[v].size += _vec[r].size;
        if constexpr (on_update) on_update(v, l, r);
    }

    void _reverse(int v) {
        int &l = _vec[v].left, &r = _vec[v].right;
        if constexpr (on_reverse) on_reverse(v, l, r);
        std::swap(l, r);
        _vec[v].rev ^= true;
    }

    void _push(int v) {
        int l = _vec[v].left, r = _vec[v].right;
        if (_vec[v].rev) {
            if (l != -1) _reverse(l);
            if (r != -1) _reverse(r);
            _vec[v].rev = false;
        }
        if constexpr (on_push) on_push(v, l, r);
    }

    int _dir(int v) const noexcept {
        int p = _vec[v].parent;
        if (p == -1) return -2;
        if (v == _vec[p].left) return 0;
        if (v == _vec[p].right) return 1;
        return -1;
    }

    // Adds `v` as a splay child of `u`.
    void _merge(int p, int c, int d) noexcept {
        if (d == 0) _vec[p].left = c;
        else if (d == 1) _vec[p].right = c;
        if (c != -1) _vec[c].parent = p;
    }

    // Rotates the splay tree and moves `v` a step closer to the splay root.
    void _rotate(int v) {
        int d = _dir(v);
        int p = _vec[v].parent;
        _merge(_vec[p].parent, v, _dir(p));
        if (d == 0) _merge(p, _vec[v].right, 0);
        else _merge(p, _vec[v].left, 1);
        _merge(v, p, 1 - d);
        _update(p);
    }

    // Moves `v` to the root of its splay tree.
    void _splay(int v) {
        while (_dir(v) >= 0 && _dir(_vec[v].parent) >= 0) {
            _push(_vec[_vec[v].parent].parent);
            _push(_vec[v].parent);
            _push(v);
            if (_dir(v) == _dir(_vec[v].parent)) _rotate(_vec[v].parent);
            else _rotate(v);
            _rotate(v);
        }
        if (_dir(v) >= 0) {
            _push(_vec[v].parent);
            _push(v);
            _rotate(v);
        }
        _push(v);
        _update(v);
    }

    // Sets `root`-to-`v` as the preferred path and splays `v`.
    void _access(int v) {
        int p = v, c = -1;
        while (p != -1) {
            _splay(p);
            _vec[p].right = c;
            _update(p);
            c = p;
            p = _vec[p].parent;
        }
        _splay(v);
    }

    // Returns the level ancestor of `v` at depth `d`.
    int _jump(int v, int d) {
        _push(v);
        int l = _vec[v].left;
        int dv = l == -1 ? 0 : _vec[l].size;
        if (d == dv) {
            _splay(v);
            return v;
        }
        if (d < dv) return _jump(l, d);
        return _jump(_vec[v].right, d - dv - 1);
    }

  public:
    link_cut_tree() {}

    // Initializes a link-cut tree with the specified number of vertices.
    link_cut_tree(int num_vertices) : _len(num_vertices) {
        assert(num_vertices >= 0);
        _vec.resize(_len);
    }

    // Exposes the vertex `v`.
    // This method should be called before:
    // - Querying `root`-to-`v` path aggegation; or
    // - Modifying aggregation-related values of `v`.
    //
    // Requires `0 <= v < num_vertices`.
    void access(int v) {
        assert(0 <= v && v < _len);
        _access(v);
    }

    // Updates the vertex `v`.
    // This method should be called after modifying aggregation-related values of `v`.
    //
    // Requires `0 <= v < num_vertices`.
    void update(int v) {
        assert(0 <= v && v < _len);
        _update(v);
    }

    // Returns the root of the tree containing `v`.
    // Requires `0 <= v < num_vertices`.
    int root(int v) {
        assert(0 <= v && v < _len);
        _access(v);
        while (_vec[v].left != -1) {
            v = _vec[v].left;
            _push(v);
        }
        _splay(v);
        return v;
    }

    // Removes the edge between `v` and its parent.
    // Requires `0 <= v < num_vertices`.
    // Requires the parent to exist.
    void cut(int v) {
        assert(0 <= v && v < _len);
        _access(v);
        assert(_vec[v].left != -1);
        _vec[_vec[v].left].parent = -1;
        _vec[v].left = -1;
        _update(v);
    }

    // Adds `p` as the parent of `v`.
    // Requires `0 <= v < num_vertices`.
    // Requires `0 <= p < num_vertices`.
    // Requires `v` to be the root of a tree.
    // Requires `v` and `p` to be disconnected.
    void link(int v, int p) {
        assert(0 <= v && v < _len);
        assert(0 <= p && p < _len);
        _access(v);
        assert(_vec[v].left == -1);
        assert(v != root(p));
        _access(p);
        _vec[v].parent = p;
    }

    // Reorients the tree containing `v` such that `v` becomes the new root.
    // Requires `0 <= v < num_vertices`.
    void reorient(int v) {
        assert(0 <= v && v < _len);
        _access(v);
        _reverse(v);
        _access(v);
    }

    // Returns the lowest common ancestor of `u` and `v`.
    // If `u` and `v` are disconnected, returns `-1`.
    // Requires `0 <= u < num_vertices`.
    // Requires `0 <= v < num_vertices`.
    int lca(int u, int v) {
        assert(0 <= u && u < _len);
        assert(0 <= v && v < _len);
        if (u == v) return u;
        _access(u);
        _access(v);
        if (_vec[u].parent == -1) return -1;
        _splay(u);
        if (_vec[u].parent == -1) return u;
        return _vec[u].parent;
    }

    // Returns the number of edges between `v` and its root.
    // Requires `0 <= v < num_vertices`.
    int depth(int v) {
        assert(0 <= v && v < _len);
        _access(v);
        if (int l = _vec[v].left; l == -1) return 0;
        else return _vec[l].size;
    }

    // Returns the level ancestor of `v` at depth `d` relative to the root.
    // If the level ancestor does not exist, returns `-1`.
    // Requires `0 <= v < num_vertices`.
    // Requires `d >= 0`.
    int level_ancestor(int v, int d) {
        assert(0 <= v && v < _len);
        assert(d >= 0);
        if (d > depth(v)) return -1;
        return _jump(v, d);
    }
};

}  // namespace kotone

#endif  // KOTONE_LINK_CUT_TREE_HPP

std::vector<int> acc, lazy;
void on_push(int p, int l, int r) {
    acc[p] += lazy[p];
    if (l != -1) lazy[l] += lazy[p];
    if (r != -1) lazy[r] += lazy[p];
    lazy[p] = 0;
}

int main() {
    int N;
    std::cin >> N;
    acc.resize(N);
    lazy.resize(N);
    kotone::link_cut_tree<nullptr, nullptr, on_push> lct(N);
    for (int i = 1; i < N; i++) {
        int u, v;
        std::cin >> u >> v;
        u--, v--;
        lct.reorient(u);
        lct.link(u, v);
    }
    int Q;
    std::cin >> Q;
    while (Q--) {
        int u, v;
        std::cin >> u >> v;
        u--, v--;
        lct.reorient(u);
        lct.access(v);
        lazy[v]++;
    }
    int64_t result = 0;
    for (int i = 0; i < N; i++) {
        lct.access(i);
        result += acc[i] * int64_t(acc[i] + 1) / 2;
    }
    std::cout << result << std::endl;
}