結果

問題 No.399 動的な領主
コンテスト
ユーザー shisidor
提出日時 2025-05-01 11:07:52
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 204 ms / 2,000 ms
コード長 1,547 bytes
コンパイル時間 4,307 ms
コンパイル使用メモリ 281,836 KB
実行使用メモリ 20,800 KB
最終ジャッジ日時 2025-05-01 11:08:01
合計ジャッジ時間 8,135 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int sizesubtree[100009], par[100009], idx[100009], fir[100009];
vector<vector<int>> G;
vector<int> tour = {0};

void dfs1(int now, int pre = -1) {
    sizesubtree[now] = 1;
    for (int &nex : G[now]) {
        if (nex == pre) continue;
        par[nex] = now;
        dfs1(nex, now);
        sizesubtree[now] += sizesubtree[nex];
        if (sizesubtree[nex] > sizesubtree[G[now][0]] || G[now][0] == pre) swap(nex, G[now][0]);
    }
}

void dfs2(int now, int a, int pre = -1) {
    fir[now] = a;
    idx[now] = tour.size();
    tour.push_back(now);
    for (int i = 0; i < (int)G[now].size(); i++) {
        int nex = G[now][i];
        if (nex == pre) continue;
        if (i == 0) dfs2(nex, a, now);
        else dfs2(nex, nex, now);
    }
}

int main() {
    int n; cin >> n;
    G.resize(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    dfs1(1); dfs2(1, 1);

    vector<ll> s(n + 2, 0);

    int q; cin >> q;
    while (q--) {
        int a, b; cin >> a >> b;
        while (fir[a] != fir[b]) {
            if (idx[fir[a]] > idx[fir[b]]) swap(a, b);
            s[idx[fir[b]]]++; s[idx[b] + 1]--;
            b = par[fir[b]];
        }
        if (idx[a] > idx[b]) swap(a, b);
        s[idx[a]]++; s[idx[b] + 1]--;
    }

    for (int i = 1; i <= n; i++) s[i] += s[i - 1];

    ll res = 0;
    for (int i = 1; i <= n; i++) res += s[i] * (s[i] + 1) / 2;
    cout << res << endl;
}
0