結果

問題 No.399 動的な領主
ユーザー btkbtk
提出日時 2016-07-14 21:31:45
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 228 ms / 2,000 ms
コード長 1,688 bytes
コンパイル時間 1,854 ms
コンパイル使用メモリ 172,048 KB
実行使用メモリ 33,092 KB
最終ジャッジ日時 2024-04-25 08:09:01
合計ジャッジ時間 4,782 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 3 ms
5,376 KB
testcase_05 AC 16 ms
5,376 KB
testcase_06 AC 224 ms
22,472 KB
testcase_07 AC 227 ms
22,596 KB
testcase_08 AC 220 ms
22,472 KB
testcase_09 AC 221 ms
22,348 KB
testcase_10 AC 3 ms
5,376 KB
testcase_11 AC 14 ms
5,376 KB
testcase_12 AC 171 ms
21,704 KB
testcase_13 AC 164 ms
21,448 KB
testcase_14 AC 138 ms
32,968 KB
testcase_15 AC 150 ms
33,092 KB
testcase_16 AC 162 ms
26,628 KB
testcase_17 AC 228 ms
22,216 KB
testcase_18 AC 227 ms
22,216 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
 
using namespace std;
typedef long long LL;
typedef vector<int> V;
typedef vector<V> Graph;
#define PB push_back
 
 
void make_tree(int v,Graph& G,V& Par,V& D, Graph& C){
    for(auto &e:G[v]){
    if(e!=Par[v]){
        C[v].PB(e);
        D[e]=D[v]+1;
        Par[e]=v;
        make_tree(e,G,Par,D,C);
    }
    }
}


//lcaの準備
void build_PP(V& P,vector<V>& PP){
    int N = P.size();
    for(int i = 0; i < N; i++)PP[0][i] = P[i];
    for(int k = 0,f=1;f; k++){
    f=0;
    for(int i = 0; i < N; i++){
        if(PP[k][i]<0)PP[k+1][i]=-1;
        else {PP[k+1][i]=PP[k][PP[k][i]];f=1;}
    }
    }
}
int lca(int u,int v,V& D,vector<V> &PP){
    if(D[u] > D[v])swap(u,v);
    for(int k = 0,d;(d=D[v]-D[u]); k++)if((d >> k) & 1)v=PP[k][v];
    if(u==v)return v;
    for(int k = PP.size() - 1; k >=0 ; k--){
        if(PP[k][u]!=PP[k][v]){
            u=PP[k][u];
            v=PP[k][v];
        }
    }
    return PP[0][u];
}

LL dfs(int v,vector<LL>& val,Graph &C){
    LL res=0;
    for(auto &u:C[v]){
    res+=dfs(u,val,C);
    val[v]+=val[u];
    }
    return res+val[v]*(val[v]+1)/2;
}
int main(){
    int N;
    cin>>N;
    Graph g(N+1),child(N+1);
    V depth(N+1,0),par(N+1,-1);
    vector<V> parpar(20,V(N+1,-1));
    vector<LL> val(N+1,0);
    g[0].push_back(1);
    for(int i=1;i<N;i++){
    int u,v;
    cin>>u>>v;
    g[u].push_back(v);
    g[v].push_back(u);
    }
    make_tree(0,g,par,depth,child);
    build_PP(par,parpar);
    
    int Q;
    cin>>Q;
    while(Q--){
    int a,b;
    cin>>a>>b;
    int ca=lca(a,b,depth,parpar);
    int cp=par[ca];
    val[a]++,val[b]++,val[ca]--,val[cp]--;
    }
    cout<<dfs(0,val,child)<<endl;
    
}
0