[SHOI2012]魔法树

洛咕

题意:n个节点的树,每个点的初始点权为0,两种操作,一个是将((u,v))路径上的每个点的点权加上(d),一个是询问以(x)节点为根的子树的权值和.(n,m<=100000.)

树链剖分+线段树模板题.操作一是区间增加,操作二是区间查询.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=100005;
int tot,head[N],nxt[N<<1],to[N<<1];
inline void add(int a,int b){
	nxt[++tot]=head[a];head[a]=tot;to[tot]=b;
}
int fa[N],seg[N],rev[N<<2],top[N],dep[N],size[N],son[N];
ll ans,sum[N<<2],Add[N<<2];
inline void dfs1(int u,int father){
	size[u]=1;
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];if(v==father)continue;
		dep[v]=dep[u]+1;fa[v]=u;
		dfs1(v,u);size[u]+=size[v];
		if(size[v]>size[son[u]])son[u]=v;
	}
}
inline void dfs2(int u,int father){
	if(son[u]){
		seg[son[u]]=++seg[0];
		rev[seg[0]]=son[u];
		top[son[u]]=top[u];
		dfs2(son[u],u);
	}
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];
		if(!top[v]){
			seg[v]=++seg[0];
			rev[seg[0]]=v;
			top[v]=v;
			dfs2(v,u);
		}
	}
}
inline void build(int p,int l,int r){
	if(l==r){sum[p]=0;return;}
	int mid=(l+r)>>1;build(p<<1,l,mid);build(p<<1|1,mid+1,r);
	sum[p]=sum[p<<1]+sum[p<<1|1];
}
inline void pushdown(int p,int l,int r,int mid){
	if(!Add[p])return;
	Add[p<<1]+=Add[p];Add[p<<1|1]+=Add[p];
	sum[p<<1]+=(mid-l+1)*Add[p];sum[p<<1|1]+=(r-mid)*Add[p];
	Add[p]=0;
}
inline void modify(int p,int l,int r,int ql,int qr,int v){
	if(ql<=l&&qr>=r){
		Add[p]+=v;sum[p]+=1ll*(r-l+1)*v;return;
	}
	int mid=(l+r)>>1;pushdown(p,l,r,mid);
	if(ql<=mid)modify(p<<1,l,mid,ql,qr,v);
	if(qr>mid)modify(p<<1|1,mid+1,r,ql,qr,v);
	sum[p]=sum[p<<1]+sum[p<<1|1];
}
inline void change(int x,int y,int z){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		modify(1,1,seg[0],seg[top[x]],seg[x],z);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])swap(x,y);
	modify(1,1,seg[0],seg[x],seg[y],z);
}
inline void query(int p,int l,int r,int ql,int qr){
	if(ql<=l&&qr>=r){ans+=sum[p];return;}
	int mid=(l+r)>>1;pushdown(p,l,r,mid);
	if(ql<=mid)query(p<<1,l,mid,ql,qr);
	if(qr>mid)query(p<<1|1,mid+1,r,ql,qr);
}
int main(){
	int n=read();
	for(int i=1;i<n;++i){
		int a=read()+1,b=read()+1;
		add(a,b);add(b,a);
	}
	seg[0]=seg[1]=rev[1]=top[1]=dep[1]=1;
	dfs1(1,0);dfs2(1,0);build(1,1,seg[0]);
	int m=read();
	while(m--){
		char ch;cin>>ch;
		if(ch=='A'){
			int x=read()+1,y=read()+1,z=read();
			change(x,y,z);
		}
		if(ch=='Q'){
			int x=read()+1;ans=0;query(1,1,seg[0],seg[x],seg[x]+size[x]-1);
			printf("%lld
",ans);
		}
	}
    return 0;
}