結果

問題 No.399 動的な領主
ユーザー conf
提出日時 2016-07-15 23:46:30
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 232 ms / 2,000 ms
コード長 1,616 bytes
コンパイル時間 717 ms
コンパイル使用メモリ 74,328 KB
実行使用メモリ 22,656 KB
最終ジャッジ日時 2024-11-07 19:14:04
合計ジャッジ時間 3,841 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX_V 100000
#define MAX_LOG_V 17

vector<int> G[MAX_V];
int root=0;
int parent[MAX_LOG_V][MAX_V];
int depth[MAX_V];

void dfs(int v, int p, int d){
    parent[0][v]=p;
    depth[v]=d;
    for(auto &e:G[v]){
        if(e!=p) dfs(e,v,d+1);
    }
}

void init(int V){
    dfs(root,-1,0);
    for(int k=0;k+1<MAX_LOG_V;k++){
        for(int v=0;v<V;v++){
            if(parent[k][v]<0) parent[k+1][v]=-1;
            else parent[k+1][v]=parent[k][parent[k][v]];
        }
    }
}

int lca(int u, int v){
    if(depth[u]>depth[v])swap(u,v);
    for(int k=0;k<MAX_LOG_V;k++){
        if((depth[v]-depth[u])>>k&1) v=parent[k][v];
    }
    if(u==v) return u;
    for(int k=MAX_LOG_V-1;k>=0;k--){
        if(parent[k][u]!=parent[k][v]){
            u=parent[k][u];
            v=parent[k][v];
        }
    }
    return parent[0][u];
}

int go[MAX_V];
int turn[MAX_V];
int path[MAX_V];

int dfs2(int v, int p){
    int n=go[v];
    for(auto &e:G[v]){
        if(e!=p) n+=dfs2(e,v);
    }
    path[v]=n-turn[v];
    return n-2*turn[v];
}

int main(){
    int N;
    cin>>N;
    for(int i=1;i<N;i++){
        int u,v;
        cin>>u>>v;
        G[u-1].push_back(v-1);
        G[v-1].push_back(u-1);
    }
    init(N);
    int Q;
    cin>>Q;
    for(int i=0;i<Q;i++){
        int A,B;
        cin>>A>>B;
        A--;B--;
        turn[lca(A,B)]++;
        go[A]++;go[B]++;
    }
    dfs2(0,-1);
    long long int ans=0;
    for(int i=0;i<N;i++){
        ans+=(long long int)path[i]*(path[i]+1)/2;
    }
    cout<<ans<<endl;
    return 0;
}
0