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

• 問題: No.399 動的な領主
• ユーザー: K2
• 提出日時: 2026-03-19 03:31:32
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 90 ms / 2,000 ms
• コード長: 3,404 bytes
• コンパイル時間: 4,761 ms
• コンパイル使用メモリ: 381,524 KB
• 実行使用メモリ: 26,416 KB
• 最終ジャッジ日時: 2026-03-19 03:31:41
• 合計ジャッジ時間: 9,082 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge1_1

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

ソースコード

#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;

using ll = long long;
using mint = modint998244353;
// using mint = modint1000000007;

template <typename T> using vec = vector<T>;
template <typename T> using pa = pair<T, T>;
template <typename T> using mipq = priority_queue<T, vec<T>, greater<T>>;

#define REP(_1, _2, _3, _4, name, ...) name
#define REP1(i, n) for (auto i = decay_t<decltype(n)>{}; (i) < (n); ++(i))
#define REP2(i, l, r) for (auto i = (l); (i) < (r); ++(i))
#define REP3(i, l, r, d) for (auto i = (l); (i) < (r); i += (d))
#define rep(...) REP(__VA_ARGS__, REP3, REP2, REP1)(__VA_ARGS__)
#define rrep(i, r, l) for (int i = (r); i >= (l); --i)
template <typename T> bool chmax(T &a, const T &b) { return (a < b ? a = b, true : false); }
template <typename T> bool chmin(T &a, const T &b) { return (a > b ? a = b, true : false); }

constexpr int INF = 1 << 30;
constexpr ll LINF = 1LL << 60;
constexpr int mov[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

void solve();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    int T = 1;
    // cin >> T;
    while (T--) solve();
}

struct LCA {
    vector<vector<int>> G, parent;
    vector<int> depth;
    int N, h;
    LCA(const vector<vector<int>> &G) : G(G) {
        N = G.size();
        h = 1;
        while ((1 << h) < N) h++;
        parent.assign(h, vector<int>(N, -1));
        depth.assign(N, -1);
        dfs(0, -1, 0);
        for (int k = 0; k < h - 1; k++) {
            for (int v = 0; v < N; v++) {
                if (parent[k][v] < 0)
                    parent[k + 1][v] = -1;
                else
                    parent[k + 1][v] = parent[k][parent[k][v]];
            }
        }
    }
    void dfs(int v, int p, int d) {
        parent[0][v] = p;
        depth[v] = d;
        for (int nv : G[v]) {
            if (nv == p) continue;
            dfs(nv, v, d + 1);
        }
    }
    int query(int u, int v) {
        if (depth[u] > depth[v]) swap(u, v);
        int diff = depth[v] - depth[u];
        for (int k = 0; k < h; k++) {
            if ((diff >> k) & 1) {
                v = parent[k][v];
            }
        }
        if (u == v) return u;
        for (int k = h - 1; k >= 0; k--) {
            if (parent[k][u] != parent[k][v]) {
                u = parent[k][u];
                v = parent[k][v];
            }
        }
        return parent[0][u];
    }
    int dist(int u, int v) {
        return depth[u] + depth[v] - 2 * depth[query(u, v)]; 
    }
    int par(int u) {
        return parent[0][u];
    }
};

void solve() {
    int N;
    cin >> N;
    vec<vec<int>> G(N);
    rep(i, N - 1) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    LCA lca(G);

    vec<int> s(N);
    int Q;
    cin >> Q;
    while (Q--) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        int l = lca.query(a, b);
        s[a]++; s[b]++;
        s[l]--;
        l = lca.par(l);
        if (l != -1) s[l]--;
    }

    ll ans = 0;
    auto dfs = [&] (auto self, int u, int p) -> void {
        for (auto v : G[u]) {
            if (v == p) continue;
            self(self, v, u);
            s[u] += s[v];
        }
        ans += (ll)s[u] * (s[u] + 1) / 2;
    };
    dfs(dfs, 0, -1);
    cout << ans << '\n';
}