#1181681 (C++17) No.2163 LCA Sum Query

• 問題: No.2163 LCA Sum Query
• ユーザー: vjudge1
• 提出日時: 2026-08-30 22:23:38
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0)
• 結果: AC
• 実行時間: 348 ms / 6,000 ms
• コード長: 3,115 bytes
• コンパイル時間: 1,575 ms
• コンパイル使用メモリ: 225,224 KB
• 実行使用メモリ: 18,204 KB
• 最終ジャッジ日時: 2026-08-30 22:23:51
• 合計ジャッジ時間: 12,323 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
sample	AC * 2
other	AC * 40

ソースコード

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e4+5;
int n,q,co[N],tot;
int fa[N],sz[N],son[N],dp[N],seg[N],tp[N],rev[N];
vector<int>e[N];
#define L k<<1
#define R k<<1|1
ll s0[N<<2],s1[N<<2],s2[N<<2],tg[N<<2],ans;
void dfs1(int x){
	sz[x]=1;
	for(auto v:e[x])if(!sz[v]){
		dp[v]=dp[x]+1,fa[v]=x;
		dfs1(v);
		sz[x]+=sz[v];
		if(sz[v]>sz[son[x]])son[x]=v;
	}
}
void dfs2(int x,int t){
	tp[x]=t,seg[x]=++seg[0],rev[seg[0]]=x;
	if(son[x])dfs2(son[x],t);
	for(auto v:e[x])if(!tp[v])dfs2(v,v);
}
int lca(int x,int y){
	for(int fx=tp[x],fy=tp[y];fx!=fy;x=fa[fx],fx=tp[x])if(dp[fx]<dp[fy])swap(x,y),swap(fx,fy);
	return dp[x]<dp[y]?x:y;
}
void pushtg(int k,ll v){
	tg[k]+=v;
	s2[k]=s2[k]+2ll*s1[k]*v+1ll*s0[k]*v*v;
	s1[k]=s1[k]+1ll*s0[k]*v;
}
void pushdown(int k){
	if(tg[k]){
		pushtg(L,tg[k]);
		pushtg(R,tg[k]);
		tg[k]=0;
	}
}
void pushup(int k){
	s2[k]=s2[L]+s2[R];
	s1[k]=s1[L]+s1[R];
}
void modify(int k,int l,int r,int x,int y,int v){
	if(x<=l&&r<=y)return pushtg(k,v);
	int mid=l+r>>1;
	pushdown(k);
	if(x<=mid)modify(L,l,mid,x,y,v);
	if(y>mid)modify(R,mid+1,r,x,y,v);
	pushup(k);
}
ll query(int k,int l,int r,int x,int y){
	if(x<=l&&r<=y)return s2[k]-s1[k];
	int mid=l+r>>1;ll res=0;
	pushdown(k);
	if(x<=mid)res+=query(L,l,mid,x,y);
	if(y>mid)res+=query(R,mid+1,r,x,y);
	return res;
}
ll Query(int k,int l,int r,int x,int y){
	if(x<=l&&r<=y)return 2ll*tot*s1[k]-1ll*tot*tot*s0[k]-s2[k]-s1[k]+1ll*tot*s0[k];
	int mid=l+r>>1;ll res=0;
	pushdown(k);
	if(x<=mid)res+=Query(L,l,mid,x,y);
	if(y>mid)res+=Query(R,mid+1,r,x,y);
	return res;
}
int qsz(int k,int l,int r,int x){
	if(l==r)return tg[k];
	int mid=l+r>>1;
	pushdown(k);
	if(x<=mid)return qsz(L,l,mid,x);
	else return qsz(R,mid+1,r,x);
}
void upd(int x,int v){
	tot+=v,co[x]^=1;
	for(int fx=tp[x];x;x=fa[fx],fx=tp[x])modify(1,1,n,seg[fx],seg[x],v);
}
void build(int k,int l,int r){
	if(l==r){
		l=rev[l];
		s0[k]=l-fa[l];
		return;
	}
	int mid=l+r>>1;
	build(L,l,mid),build(R,mid+1,r);
	s0[k]=s0[L]+s0[R];
}
int kth(int x,int k){
	while(dp[x]-dp[tp[x]]<k)k-=dp[x]-dp[tp[x]]+1,x=fa[tp[x]];
	return rev[seg[x]-k];
}
void Qry(int rt,int v){
	int z=lca(rt,v);
	if(z!=v){
		int S=qsz(1,1,n,seg[v]);
		if(sz[v]>1)ans+=query(1,1,n,seg[v]+1,seg[v]+sz[v]-1);
		ans+=1ll*v*S*(S-1);
		return;
	}
	vector<pair<int,int> >tmp;
	if(rt==v)ans+=1ll*tot*(tot-1)*v;
	else{
		int u=kth(rt,dp[rt]-dp[v]-1);
		int S=qsz(1,1,n,seg[u]);
		tmp.emplace_back(seg[u],seg[u]+sz[u]-1);
		ans+=1ll*(tot-S)*(tot-S-1)*v;
	}
	for(int x=v,fx=tp[x];x;x=fa[fx],fx=tp[x]){
		ans+=Query(1,1,n,seg[fx],seg[x]);
		tmp.emplace_back(seg[fx],seg[x]);
	}
	sort(tmp.begin(),tmp.end());
	for(int i=1;i<tmp.size();++i)if(tmp[i-1].second+1<tmp[i].first)ans+=query(1,1,n,tmp[i-1].second+1,tmp[i].first-1);
	if(tmp.back().second<n)ans+=query(1,1,n,tmp.back().second+1,n);
}
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1,x,y;i<n;++i){
		scanf("%d%d",&x,&y);
		e[x].push_back(y),e[y].push_back(x);
	}
	dfs1(1),dfs2(1,1);
	build(1,1,n);
	for(int i=1,u,r,v;i<=q;++i){
		scanf("%d%d%d",&u,&r,&v);
		upd(u,co[u]?-1:1);
		ans=0;
		Qry(r,v);
		printf("%lld\n",ans/2);
	}
	return 0;
}