結果

問題 No.399 動的な領主
ユーザー btkbtk
提出日時 2016-07-14 17:27:26
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 163 ms / 2,000 ms
コード長 1,689 bytes
コンパイル時間 1,984 ms
コンパイル使用メモリ 175,432 KB
実行使用メモリ 32,996 KB
最終ジャッジ日時 2024-11-07 18:30:53
合計ジャッジ時間 4,110 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 11 ms
5,248 KB
testcase_06 AC 163 ms
22,500 KB
testcase_07 AC 162 ms
22,480 KB
testcase_08 AC 155 ms
22,116 KB
testcase_09 AC 149 ms
22,244 KB
testcase_10 AC 3 ms
5,248 KB
testcase_11 AC 8 ms
5,248 KB
testcase_12 AC 97 ms
21,604 KB
testcase_13 AC 95 ms
21,468 KB
testcase_14 AC 78 ms
32,996 KB
testcase_15 AC 88 ms
32,912 KB
testcase_16 AC 92 ms
26,728 KB
testcase_17 AC 144 ms
22,240 KB
testcase_18 AC 145 ms
22,244 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
 
struct INIT{INIT(){ios::sync_with_stdio(false);cin.tie(0);}}init;
 
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