結果

問題 No.399 動的な領主
ユーザー nxterunxteru
提出日時 2019-02-08 22:33:24
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 657 ms / 2,000 ms
コード長 1,887 bytes
コンパイル時間 3,910 ms
コンパイル使用メモリ 171,388 KB
実行使用メモリ 23,460 KB
最終ジャッジ日時 2023-09-14 03:50:59
合計ジャッジ時間 8,623 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
11,688 KB
testcase_01 AC 5 ms
11,840 KB
testcase_02 AC 5 ms
11,704 KB
testcase_03 AC 6 ms
11,724 KB
testcase_04 AC 7 ms
11,748 KB
testcase_05 AC 42 ms
12,060 KB
testcase_06 AC 641 ms
15,600 KB
testcase_07 AC 612 ms
15,568 KB
testcase_08 AC 609 ms
15,584 KB
testcase_09 AC 625 ms
15,536 KB
testcase_10 AC 9 ms
11,756 KB
testcase_11 AC 33 ms
12,260 KB
testcase_12 AC 438 ms
15,996 KB
testcase_13 AC 419 ms
16,008 KB
testcase_14 AC 145 ms
23,252 KB
testcase_15 AC 174 ms
23,460 KB
testcase_16 AC 256 ms
19,324 KB
testcase_17 AC 657 ms
15,484 KB
testcase_18 AC 620 ms
15,548 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PB push_back
struct SEG{
	ll seg[1<<18],la[1<<18];
	SEG(void){
		for(int i=0;i<1<<18;i++){
			seg[i]=0;
			la[i]=0;
		}
	}
	void lazy(ll l,ll r,int k){
		if(la[k]!=0){
			seg[k]+=(r-l+1)*la[k];
			if(l!=r){
				la[k*2+1]+=la[k];
				la[k*2+2]+=la[k];
			}
			la[k]=0;
		}
	}
	void add(int a,int b,int l,int r,int k,ll x){
		if(r<a||b<l){
			lazy(l,r,k);
			return;
		}
		if(a<=l&&r<=b){
			la[k]+=x;
			lazy(l,r,k);
			return;
		}
		lazy(l,r,k);
		add(a,b,l,(l+r)/2,k*2+1,x);
		add(a,b,(l+r)/2+1,r,k*2+2,x);
		seg[k]=seg[k*2+1]+seg[k*2+2];
	}
	ll sum(int a,int b,int l,int r,int k){
		lazy(l,r,k);
		if(r<a||b<l)return 0;
		if(a<=l&&r<=b)return seg[k];
		return sum(a,b,l,(l+r)/2,k*2+1)+sum(a,b,(l+r)/2+1,r,k*2+2);
	}
};
int n,q,dp[100005],sz[100005],vs[100005],id[100005],hd[100005],cn[100005],k;
vector<int>g[100005];
void dfs1(int v,int p){
	sz[v]=1;
	for(int i=0;i<g[v].size();i++){
		if(g[v][i]!=p){
			dfs1(g[v][i],v);
			sz[v]+=sz[g[v][i]];
			if(sz[g[v][i]]>sz[g[v][0]])swap(g[v][i],g[v][0]);
		}
	}
}
void dfs2(int v,int p,int d,int h){
	vs[k]=v;
	id[v]=k;
	hd[k]=h;
	cn[k]=cn[h];
	dp[k]=d;
	k++;
	for(int i=0;i<g[v].size();i++){
		if(g[v][i]!=p){
			if(i!=0)cn[k]=id[v];
			dfs2(g[v][i],v,d+1,i==0?h:k);
		}
	}
}
SEG seg;
ll ans=0;
int main(void){
	scanf("%d",&n);
	for(int i=0;i<n-1;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		g[--a].PB(--b);
		g[b].PB(a);
	}
	dfs1(0,-1);
	dfs2(0,-1,0,0);
	for(int i=0;i<n;i++)seg.add(i,i,0,(1<<17)-1,0,1);
	scanf("%d",&q);
	while(q--){
		int a,b;
		scanf("%d%d",&a,&b);
		a--,b--;
		a=id[a],b=id[b];
		while(hd[a]!=hd[b]){
			if(dp[hd[a]]<dp[hd[b]])swap(a,b);
			ans+=seg.sum(hd[a],a,0,(1<<17)-1,0);
			seg.add(hd[a],a,0,(1<<17)-1,0,1);
			a=cn[a];
		}
		if(a>b)swap(a,b);
		ans+=seg.sum(a,b,0,(1<<17)-1,0);
		seg.add(a,b,0,(1<<17)-1,0,1);
	}
	printf("%lld\n",ans);
}
0