結果

問題 No.399 動的な領主
コンテスト
ユーザー nxteru
提出日時 2019-02-08 22:33:24
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 667 ms / 2,000 ms
コード長 1,887 bytes
コンパイル時間 1,930 ms
コンパイル使用メモリ 175,940 KB
実行使用メモリ 23,380 KB
最終ジャッジ日時 2024-07-01 11:39:06
合計ジャッジ時間 8,449 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

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