树剖 RE 80分求调
查看原帖
树剖 RE 80分求调
491532
艾德加楼主2022/11/9 09:07
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,u,v,d,a,b,chuo=0,dep[800003],hs[800003],siz[800003],dfn[800003],pp[800003],topf[800003],sum[800003],laz[800003],last[8000003];
char ch;
struct nod{
	int to,gg;
}e[400003];
int cnt=0;
void add(int x,int y){
	e[++cnt].to=y;
	e[cnt].gg=last[x];
	last[x]=cnt;
}
void dfs1(int x,int fa){
	siz[x]=1;
	pp[x]=fa;
	dep[x]=dep[fa]+1; 
	for(int i=last[x];i;i=e[i].gg){
		int y=e[i].to;
		if(y==fa) continue ;
		dfs1(y,x);
		if(siz[hs[x]]<siz[y]) hs[x]=y;
		siz[x]+=siz[y];
	}
}
void dfs2(int x,int tp){
	dfn[x]=++chuo;
	topf[x]=tp;
	if(hs[x]) dfs2(hs[x],tp); 
	for(int i=last[x];i;i=e[i].gg){
		int y=e[i].to;
		if(y==pp[x]||y==hs[x]) continue ;
		dfs2(y,y);
	}
}
void pushup(int l,int r,int pos){
	int mi=(l+r)>>1;
	sum[pos<<1]+=(laz[pos]*(mi-l+1));
	sum[pos<<1|1]+=(laz[pos]*(r-mi));
	laz[pos<<1]+=laz[pos];
	laz[pos<<1|1]+=laz[pos];laz[pos]=0;
}
void upd(int ql,int qr,int l,int r,int pos,int da){
	if(l>=ql&&r<=qr){
		sum[pos]+=(r-l+1)*da;
		laz[pos]+=da;
		return ;
	}
	pushup(l,r,pos);
	int mi=(l+r)>>1;
	if(mi>=ql) upd(ql,qr,l,mi,pos<<1,da);
	if(mi<qr) upd(ql,qr,mi+1,r,pos<<1|1,da);
	sum[pos]=sum[pos<<1|1]+sum[pos<<1];
	return ;
}
int que(int ql,int qr,int l,int r,int pos){
	if(l>=ql&&r<=qr) return sum[pos];
	pushup(l,r,pos);
	int mi=(l+r)>>1;
	int ans=0;
	if(mi>=ql) ans=que(ql,qr,l,mi,pos<<1);
	if(mi<qr) ans=ans+que(ql,qr,mi+1,r,pos<<1|1);
	return ans;
}
void xiu(int fr,int de,int x){//fr应该比de深度大 
	if(dep[fr]<dep[de]) swap(fr,de);
	while(1){
		if(topf[fr]==topf[de]){
			//cout<<dfn[de]<<" "<<dfn[fr]<<endl;
			upd(dfn[de],dfn[fr],1,n,1,x);
			break;
		}
		else{
			upd(dfn[topf[fr]],dfn[fr],1,n,1,x);
			fr=pp[topf[fr]];
		}
		if(dep[fr]<dep[de]) swap(fr,de);
	}
}
signed main(){
	cin>>n;
	for(int i=1;i<n;i++){
		scanf("%lld%lld",&a,&b);
		a++,b++;
		add(a,b);
		add(b,a);
	}
	dfs1(1,0);
	dfs2(1,1);
	cin>>q;
	while(q--){
		cin>>ch;
		scanf("%lld",&u);
		u++;
		if(ch=='A'){
			scanf("%lld%lld",&v,&d);
			v++;
			xiu(u,v,d);
		}
		else{
			printf("%lld\n",que(dfn[u],dfn[u]+siz[u]-1,1,n,1));
		}
	}
}
2022/11/9 09:07
加载中...