結果

問題 No.399 動的な領主
コンテスト
ユーザー face4
提出日時 2019-11-19 14:20:31
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 180 ms / 2,000 ms
コード長 1,856 bytes
コンパイル時間 687 ms
コンパイル使用メモリ 72,456 KB
実行使用メモリ 25,100 KB
最終ジャッジ日時 2024-10-03 06:27:36
合計ジャッジ時間 3,357 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

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