結果

問題 No.399 動的な領主
ユーザー face4face4
提出日時 2019-11-19 14:20:31
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 256 ms / 2,000 ms
コード長 1,856 bytes
コンパイル時間 680 ms
コンパイル使用メモリ 73,872 KB
実行使用メモリ 25,220 KB
最終ジャッジ日時 2024-04-14 09:26:10
合計ジャッジ時間 4,326 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
13,080 KB
testcase_01 AC 5 ms
12,356 KB
testcase_02 AC 5 ms
12,332 KB
testcase_03 AC 6 ms
12,832 KB
testcase_04 AC 6 ms
12,716 KB
testcase_05 AC 20 ms
13,840 KB
testcase_06 AC 245 ms
17,524 KB
testcase_07 AC 249 ms
17,396 KB
testcase_08 AC 231 ms
17,452 KB
testcase_09 AC 244 ms
17,440 KB
testcase_10 AC 7 ms
13,508 KB
testcase_11 AC 19 ms
13,192 KB
testcase_12 AC 196 ms
17,888 KB
testcase_13 AC 194 ms
17,868 KB
testcase_14 AC 134 ms
25,220 KB
testcase_15 AC 149 ms
25,088 KB
testcase_16 AC 163 ms
21,208 KB
testcase_17 AC 247 ms
17,436 KB
testcase_18 AC 256 ms
17,444 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;

vector<int> v[100001], depth(100001, 0), imos(100001, 0);
int par[20][100001] = {};
int n;

void dfs(int now, int p, int d){
    par[0][now] = p;
    depth[now] = d;
    for(int child : v[now]){
        if(child == p)  continue;
        dfs(child, now, d+1);
    }
}

void init(){
    dfs(0, -1, 0);
    for(int k = 0; k+1 < 20; k++){
        for(int i = 0; i <= n; i++){
            if(par[k][i] < 0)   par[k+1][i] = -1;
            else                par[k+1][i] = par[k][par[k][i]];
        }
    }
}

int lca(int u, int v){
    // make v depper
    if(depth[u] > depth[v]) swap(u, v);
    for(int k = 0; k < 20; k++){
        // uとvのdepthの差を2べきを使ってlogオーダーで縮める
        if(((depth[v]-depth[u])>>k)&1){
            v = par[k][v];
        }
    }
    if(u == v)  return u;
    // uとvのdepthは等しいのでこれからは一緒にdepthを弄る
    for(int k = 18; k >= 0; k--){
        if(par[k][u] != par[k][v]){
            u = par[k][u];
            v = par[k][v];
        }
    }
    return par[0][u];
}

ll ans;

void dfs2(int now, int p){
    for(int child : v[now]){
        if(child == p)  continue;
        dfs2(child, now);
        imos[now] += imos[child];
    }
    ans += (ll)imos[now]*(imos[now]+1)/2;
}

// editorialを読んだ　面白い
// id-0をsuper rootとする
int main(){
    cin >> n;
    v[0].push_back(1);
    for(int i = 0; i < n-1; i++){
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    init();
    int q;
    cin >> q;
    while(q-- > 0){
        int a, b;
        cin >> a >> b;
        int l = lca(a, b);
        imos[a]++, imos[b]++, imos[l]--, imos[par[0][l]]--;
    }
    ans = 0;
    dfs2(0, -1);
    cout << ans << endl;
    return 0;
}
0