50分RE

找了好久没找出错误

大佬求调，QAQ

P3833 魔法树

测评记录

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pp p<<1
#define ppp p<<1|1
#define endl "\n"
const int N=1e6+10;
ll n,q,w[N];
ll h[N],nt[N],to[N],cnt;
ll de[N],si[N],so[N],fa[N],dfn[N],rnk[N],top[N],tot;
ll sum[N],sg[N];

void add(ll a,ll b){
	to[++cnt]=b;
	nt[cnt]=h[a];
	h[a]=cnt;
}

void dfs(ll u){
	si[u]=1;
	so[u]=-1;
	for(int i=h[u];i;i=nt[i]){
		ll w=to[i];
		if(fa[u]==w)
			continue;
		fa[w]=u;
		dfs(w);
		si[u]+=si[w];
		if(so[u]==-1||si[so[u]]<si[w])
			so[u]=w;
	}
}

void dfss(ll u,ll v){
	top[u]=v;
	dfn[u]=++tot;
	rnk[tot]=u;
	if(so[u]==-1)
		return ;
	dfss(so[u],v);
	for(int i=h[u];i;i=nt[i]){
		ll w=to[i];
		if(fa[u]!=w&&so[u]!=w)
			dfss(w,w);
	}
}

void pushup(ll s,ll t,ll p){
	sg[pp]+=sg[p];
	sg[ppp]+=sg[p];
	ll m=(s+t)>>1;
	sum[pp]+=(m-s+1)*sg[p];
	sum[ppp]+=(t-m)*sg[p];
	sg[p]=0;
}

void treeadd(ll s,ll t,ll l,ll r,ll c,ll p){
	if(l<=s&&t<=r){
		sum[p]+=(t-s+1)*c;
		sg[p]+=c;
		return ;
	}
	pushup(s,t,p);
	ll m=(s+t)>>1;
	if(l<=m)treeadd(s,m,l,r,c,pp);
	if(r>m)treeadd(m+1,t,l,r,c,ppp);
	sum[p]=sum[pp]+sum[ppp];
}

void getadd(ll x,ll y,ll c){
	ll fx=top[x],fy=top[y];
	while(fx!=fy){
		if(de[fx]>de[fy])
			treeadd(1,n,dfn[fx],dfn[x],c,1),x=fa[fx];
		else
			treeadd(1,n,dfn[fy],dfn[y],c,1),y=fa[fy];
		fx=top[x];
		fy=top[y];
	}
	treeadd(1,n,min(dfn[x],dfn[y]),max(dfn[x],dfn[y]),c,1);
}

ll getsum(ll s,ll t,ll l,ll r,ll p){
	if(l<=s&&t<=r){
		return sum[p];
	}
	pushup(s,t,p);
	ll m=(s+t)>>1,res=0;
	if(l<=m)res=getsum(s,m,l,r,pp);
	if(r>m)res+=getsum(m+1,t,l,r,ppp);
	return res;
}


int main(){
	ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<n;++i){
		ll a,b;
		cin>>a>>b;
		a++;
		b++;
		add(a,b);
		add(b,a);
	}
	de[1]=1;
	dfs(1);
	dfss(1,1);
	cin>>q;
	while(q--){
		char op;
		ll u,v,d;
		cin>>op;
		if(op=='A'){
			cin>>u>>v>>d;
			u++,v++;
			getadd(u,v,d);
		}
		else{
			cin>>u;
			u++;
			cout<<getsum(1,n,dfn[u],dfn[u]+si[u]-1,1)<<endl;
		}
	}
}