結果

問題 No.399 動的な領主
ユーザー nxterunxteru
提出日時 2019-02-08 22:30:07
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 1,887 bytes
コンパイル時間 1,613 ms
コンパイル使用メモリ 173,108 KB
実行使用メモリ 11,720 KB
最終ジャッジ日時 2023-09-14 03:49:54
合計ジャッジ時間 7,008 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
11,720 KB
testcase_01 AC 4 ms
11,672 KB
testcase_02 TLE -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
権限があれば一括ダウンロードができます

ソースコード

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[v]=k;
	id[k]=v;
	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