Lvat_s Blog

因为一棵树的子树一定在dfs序上是连续的

所以直接修改就行了

#include<cstdio>
#include<algorithm>
using namespace std;

struct Edge{
int b,next;
}e[1000005];

struct SegTree{
int l,r;
long long tag,sum;
}tree[1000005];

int n,q,en,cnt,top[400005],id[400005],pre[400005],dep[400005],son[400005],h[400005],siz[400005],fa[400005];

void AddEdge(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}

void Pushdown(int root){
if(tree[root].tag){
	tree[root*2].tag+=tree[root].tag;
	tree[root*2].sum+=tree[root].tag*(tree[root*2].r-tree[root*2].l+1);
	tree[root*2+1].tag+=tree[root].tag;
	tree[root*2+1].sum+=tree[root].tag*(tree[root*2+1].r-tree[root*2+1].l+1);
	tree[root].tag=0;
}
}

void Pushup(int root){
tree[root].sum=tree[root*2].sum+tree[root*2+1].sum;
}

void Build(int root,int l,int r){
tree[root].l=l;
tree[root].r=r;
if(l==r){
    tree[root].sum=0;
    return;
}
int mid=(l+r)/2;
Build(root*2,l,mid);
Build(root*2+1,mid+1,r);
tree[root].sum=tree[root*2].sum+tree[root*2+1].sum;
}

void Add(int root,int l,int r,long long v){
if(tree[root].l>=l && tree[root].r<=r){
	tree[root].tag+=v;
	tree[root].sum+=v*(tree[root].r-tree[root].l+1);
	return;
}
Pushdown(root);
int mid=tree[root].l+tree[root].r>>1;
if(l<=mid)Add(root*2,l,r,v);
if(r>mid)Add(root*2+1,l,r,v);
Pushup(root);
}

long long Sum(int root,int l,int r){
if(tree[root].l>=l && tree[root].r<=r){
	return tree[root].sum;
}
Pushdown(root);
int mid=tree[root].l+tree[root].r>>1;
long long ans=0;
if(l<=mid)ans+=Sum(root*2,l,r);
if(r>mid)ans+=Sum(root*2+1,l,r);
return ans;
}

void dfs1(int u,int father,int deep){
fa[u]=father;
dep[u]=deep;
siz[u]=1;
son[u]=0;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v==father)continue;
    dfs1(v,u,deep+1);
    siz[u]+=siz[v];
    if(siz[v]>siz[son[u]]){
        son[u]=v;
    }
}
}
 
void dfs2(int u,int ux){
top[u]=ux;
id[u]=++cnt;
pre[cnt]=u;
if(son[u])dfs2(son[u],ux);
else return;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v!=son[u] && v!=fa[u]){dfs2(v,v);}
}
}

void AddLine(int u,int v,long long val){
int f1=top[u],f2=top[v];
while(f1!=f2){
	if(dep[f1]<dep[f2]){swap(u,v);swap(f1,f2);}
	Add(1,id[f1],id[u],val);
	u=fa[f1];
	f1=top[u];
}
if(dep[u]>dep[v])swap(u,v);
//printf("%d %d\n",id[u],id[v]);
Add(1,id[u],id[v],val);
}

int main(){
freopen("2836.in","r",stdin);
freopen("2836.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<n;i++){
	int u,v;
	scanf("%d %d",&u,&v);
	AddEdge(u+1,v+1);
	AddEdge(v+1,u+1);
}
Build(1,1,n);
dfs1(1,0,1);
dfs2(1,1);
scanf("%d",&q);
while(q--){
	int u,v;
	long long val;
	char s[3];
	scanf("%s",s);
	if(s[0]=='A'){
		scanf("%d %d %lld",&u,&v,&val);
		AddLine(u+1,v+1,val);
	}
	if(s[0]=='Q'){
		scanf("%d",&u);
		//printf("IS:%d %d %d\n",id[u+1],siz[u+1],u+1);
		printf("%lld\n",Sum(1,id[u+1],id[u+1]+siz[u+1]-1));
	}
}
return 0;
}