树链剖分板子

对点权
例题：
题意描述：给定一棵树和节点上的值，然后执行下面操作：
I u,v,value：把u和v路径上的节点的值都加上value；
D u,v,value:把u和v路径上的节点的值都减去value；
Q u:询问节点u上的值。

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
const int maxn=50000+10;
using namespace std;
int n,m,q;
int val[maxn];
int siz[maxn],fa[maxn],dep[maxn];
int tid[maxn],tid2[maxn],tot,top[maxn],zson[maxn];//tid为对照 
vector<int> v[maxn];
struct node{
   
	int sum,lazy;
}t[maxn<<2];
void dfs1(int u,int father,int d){
   
	dep[u]=d;
	fa[u]=father;
	siz[u]=1;
	for(int i=0;i<v[u].size();i++){
   
		int t=v[u][i];
		if(t!=father){
   
			dfs1(t,u,d+1);
			siz[u]+=siz[t];
			if(zson[u]==-1||siz[t]>siz[zson[u]])
				zson[u]=t;
		}
	}
}
void dfs2(int u,int tp){
   
	top[u]=tp;
	tid[u]=++tot;
	tid2[tid[u]]=u;
	if(zson[u]==-1)	return;
	dfs2(zson[u],tp);
	for(int i=0;i<v[u].size();i++){
   
		int t=v[u][i];
		if(t!=zson[u]&&t!=fa[u])
              dfs2(t,t);

	}
}
void pushup(int k){
   
	t[k].sum=t[k*2].sum+t[k*2+1].sum;
}
void pushdown(int k,int len){
   
	if(t[k].lazy){
   
		t[k*2].lazy+=t[k].lazy;
		t[k*2+1].lazy+=t[k].lazy;
		t[k*2].sum+=(len-(len>>1))*t[k].lazy;
		t[k*2+1].sum+=(len>>1)*t[k].lazy;
		t[k].lazy=0;
	}
}
void build(int l,int r,int k){
   
	t[k].lazy=0;
	if(l==r){
   
		t[k].sum=val[tid2[l]];
		return ;
	}
	int mid=(l+r)>>1;
	build(l,mid,k*2);
	build(mid+1,r,k*2+1);
	pushup(k);
}
void update(int L,int R,int value,int l,int r,int k){
   
    if (L<=l&&r<=R){
   
        t[k].sum+=(r-l+1)*value;
        t[k].lazy+=value;
        return ;
    }
    pushdown(k,(r-l+1));
    int mid=(l+r)>>1;
    if (L<=mid) update(L,R,value,l,mid,k<<1);
    if (R>mid) update(L,R,value,mid+1,r,k<<1|1);
    pushup(k);
}

int query(int l,int r,int k,int u){
   
    if (l==r) return t[k].sum;
    pushdown(k,r-l+1);
    int mid=(l+r)>>1;
    int ans;
    if (u<=mid) ans=query(l,mid,k<<1,u);
    else ans=query(mid+1,r,k<<1|1,u);
    pushup(k);
    return ans;
}
void solve(int x,int y,int value){
   
	int f1=top[x],f2=top[y];
	while(f1!=f2){
   
		if(dep[f1]<dep[f2]){
   
			swap(f1,f2);
			swap(x,y);
		}
		update(tid[f1],tid[x],value,1,n,1);
		x=fa[f1]; f1=top[x];
	}
	if(dep[x]<dep[y])	swap(x,y);
	update(tid[y],tid[x],value,1,n,1);
}
int main(){
   
	while(scanf("%d%d%d",&n,&m,&q)!=EOF){
   
		memset(t,0,sizeof(t));
		memset(zson,-1,sizeof(zson));
		tot=0;
		for(int i=1;i<=n;i++)
			v[i].clear();
		for(int i=1;i<=n;i++)
			scanf("%d",&val[i]);
		int x,y;
		for(int i=0;i<m;i++){
   
			scanf("%d%d",&x,&y);
			v[x].push_back(y);
			v[y].push_back(x);
		}
		dfs1(1,0,0);
		dfs2(1,1);
		build(1,n,1);
		while(q--){
   
			char s[4];
			scanf("%s",s);
			if(s[0]=='Q'){
   
				int xx;
				scanf("%d",&xx);
				printf("%d\n",query(1,n,1,tid[xx])); 
			} 
			else{
   
				int xx,yy,val;
				scanf("%d%d%d",&xx,&yy,&val);
				if(s[0]=='D')	val=-val;
				solve(xx,yy,val);
			}
		}
	}
	return 0;
}