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

• 問題: No.399 動的な領主
• ユーザー: K2
• 提出日時: 2026-03-19 03:16:57
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 752 ms / 2,000 ms
• コード長: 4,362 bytes
• コンパイル時間: 5,465 ms
• コンパイル使用メモリ: 396,324 KB
• 実行使用メモリ: 28,340 KB
• 最終ジャッジ日時: 2026-03-19 03:17:11
• 合計ジャッジ時間: 13,282 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_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 HLDecomposition {
  private:
    void dfs_size(int u) {
        size[u] = 1;
        if (G[u][0] == par[u]) swap(G[u][0], G[u].back());
        for (auto &v : G[u]) {
            if (v == par[u]) continue;
            par[v] = u;
            dfs_size(v);
            size[u] += size[v];
            if (size[v] > size[G[u][0]]) swap(v, G[u][0]);
        }
    }

    void dfs_hld(int u, int &k) {
        in[u] = k++;
        for (auto v : G[u]) {
            if (v == par[u]) continue;
            head[v] = (v == G[u][0] ? head[u] : v);
            dfs_hld(v, k);
        }
        out[u] = k;
    }

    // [u -> v)
    vector<pair<int, int>> ascend(int u, int v) const {
        vector<pair<int, int>> res;
        while (head[u] != head[v]) {
            res.emplace_back(in[u], in[head[u]]);
            u = par[head[u]];
        }
        if (u != v) res.emplace_back(in[u], in[v] + 1);
        return res;
    }

    // (u -> v]
    vector<pair<int, int>> descend(int u, int v) const {
        if (u == v) return {};
        if (head[u] == head[v]) return {{in[u] + 1, in[v]}};
        auto res = descend(u, par[head[v]]);
        res.emplace_back(in[head[v]], in[v]);
        return res;
    }

  public:
    vector<vector<int>> G;
    int root;
    vector<int> size, in, out, head, par;
    HLDecomposition(vector<vector<int>> &_G, int _root = 0) :
        G(_G),
        root(_root),
        size(G.size()),
        in(G.size(), -1),
        out(G.size(), -1),
        head(G.size(), root),
        par(G.size(), root) 
    {
        dfs_size(root);
        int k = 0;
        dfs_hld(root, k);
    }

    void path_query(int u, int v, auto &f, bool vertex = false) {
        int l = lca(u, v);
        for (auto&& [a, b] : ascend(u, l)) f(a + 1, b);
        if (vertex) f(in[l], in[l] + 1);
        for (auto&& [a, b] : descend(l, v)) f(a, b + 1);
    }

    void subtree_query(int u, auto &f, bool vertex = false) {
        f(in[u] + !f, out[u]);
    }

    int lca(int u, int v) {
        while (head[u] != head[v]) {
            if (in[u] > in[v]) swap(u, v);
            v = par[head[v]];
        }
        return in[u] < in[v] ? u : v;
    }

    int idx(int u) { return in[u]; }
};

// lazy_segtreeで
// 区間加算区間和

struct S {
    ll val;
    int siz;
};
using F = ll;

S op(S a, S b) { return {a.val + b.val, a.siz + b.siz}; }
S e() { return {0, 0}; }
S mapping(F f, S x) { return {x.val + f * x.siz, x.siz}; }
F composition(F f, F g) { return f + g; }
F id() { return 0; }

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);
    }

    HLDecomposition hld(G);
    lazy_segtree<S, op, e, F, mapping, composition, id> seg(vec<S>(N, {0, 1}));

    int Q;
    cin >> Q;
    ll ans = 0;
    auto apply = [&] (int u, int v) {
        if (u > v) swap(u, v);
        seg.apply(u, v, 1);
        ans += seg.prod(u, v).val;
    };
    while (Q--) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        hld.path_query(a, b, apply, true);
    }
    cout << ans << '\n';
}