hdu 3966 树链剖分 点操作

/*by SilverN*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
using namespace std;
const int mxn=100010;
int read() {
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0' || ch>'9') {
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9') {
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
//读入优化
struct edge {
	int v,nxt;
} e[mxn<<1];
int hd[mxn],mct=0;
void add_edge(int u,int v) {
	e[++mct].v=v;
	e[mct].nxt=hd[u];
	hd[u]=mct;
}
//邻接表
struct node {
	//结点u的 父亲 重儿子
	int fa,son;
	int size,dep,top;//子树大小 深度 重链顶点
	int w,e;//编号 对应线段树的结尾
} tr[mxn];
//树剖结点
struct segtree {
	LL smm,mk;
} st[mxn<<2];
int sz=0;
//线段树
int n,M,rt;
int w[mxn];//初始值
//
void DFS1(int u) {
	tr[u].size=1;
	tr[u].son=0;
	for(int i=hd[u]; i; i=e[i].nxt) {
		int v=e[i].v;
		if(v==tr[u].fa)continue;
		tr[v].fa=u;
		tr[v].dep=tr[u].dep+1;
		DFS1(v);
		tr[u].size+=tr[v].size;
		if(tr[v].size>tr[tr[u].son].size)
			tr[u].son=v;
	}
	return;
}
void DFS2(int u,int top) { //当前点，当前链的顶点
	tr[u].top=top;
	tr[u].w=++sz;//把树边挂上线段树
	if(tr[u].son) {
		DFS2(tr[u].son,top);//扩展搭建重链
		for(int i=hd[u]; i; i=e[i].nxt) {
			int v=e[i].v;
			if(v!=tr[u].fa && v!=tr[u].son)
				DFS2(v,v);//搭建轻链
		}
	}
	tr[u].e=sz;//当前点对应的线段树结尾
	return;
}
void update(int L,int R,LL w,int l,int r,int k) { //区间加值
	if(L<=l && r<=R) {
		st[k].mk+=w;
		st[k].smm+=(r-l+1)*w;
		return;
	}
	int mid=(l+r)>>1;
	if(st[k].mk) {
		st[k<<1].mk+=st[k].mk;
		st[k<<1].smm+=st[k].mk*(mid-l+1);
		st[k<<1|1].mk+=st[k].mk;
		st[k<<1|1].smm+=st[k].mk*(r-mid);
		st[k].mk=0;
	}
	if(L<=mid)update(L,R,w,l,mid,k<<1);
	if(R>mid)update(L,R,w,mid+1,r,k<<1|1);
	st[k].smm=(st[k<<1].smm+st[k<<1|1].smm);
	return;
}
int query(int L,int R,int l,int r,int k) {
	if(L<=l && r<=R)return st[k].smm;
	int mid=(l+r)>>1;
	if(st[k].mk) {
		st[k<<1].mk+=st[k].mk;
		st[k<<1].smm+=st[k].mk*(mid-l+1);
		st[k<<1|1].mk+=st[k].mk;
		st[k<<1|1].smm+=st[k].mk*(r-mid);
		st[k].mk=0;
	}
	LL res=0;
	if(L<=mid)res=(res+query(L,R,l,mid,k<<1));
	if(R>mid)res=(res+query(L,R,mid+1,r,k<<1|1));
	return res;
}
// 表示求树从x到y结点最短路径上所有节点的值之和
int find(int x,int y) {
	int f1=tr[x].top,f2=tr[y].top;
	int ans=0;
	while(f1!=f2) {
		if(tr[f1].dep<tr[f2].dep) {
			ans+=query(tr[f2].w,tr[y].w,1,n,1);
			y=tr[f2].fa;
			f2=tr[y].top;
		} else {
			ans+=query(tr[f1].w,tr[x].w,1,n,1);
			x=tr[f1].fa;
			f1=tr[x].top;
		}
	}
	if(tr[x].dep<tr[y].dep)return ans+query(tr[x].w,tr[y].w,1,n,1);
	return ans+query(tr[y].w,tr[x].w,1,n,1);
}
void add(int x,int y,int k) { //x到y的路径加k
	int f1=tr[x].top,f2=tr[y].top;
	while(f1!=f2) {
		if(tr[f1].dep<tr[f2].dep) {
			update(tr[f2].w,tr[y].w,k,1,n,1);
			y=tr[f2].fa;
			f2=tr[y].top;
		} else {
			update(tr[f1].w,tr[x].w,k,1,n,1);
			x=tr[f1].fa;
			f1=tr[x].top;
		}
	}
	if(tr[x].dep<tr[y].dep) update(tr[x].w,tr[y].w,k,1,n,1);
	else update(tr[y].w,tr[x].w,k,1,n,1);
	return;
}
//
int main() {
	rt = 1;
	int q;
	while(scanf("%d %d %d",&n,&M,&q)==3) {
		int i,j;
		for(i=1; i<=n; i++) {
			w[i]=read();
		}
		int x,y,k;
		mct = 0; sz = 0;
		memset(hd,0,sizeof(hd));
		memset(st,0,sizeof(st));
		for(i=1; i<n; i++) {
			x=read();
			y=read();
			add_edge(x,y);
			add_edge(y,x);
		}
		sz=tr[0].size=tr[rt].dep=0;
		//
		DFS1(rt);
		DFS2(rt,rt);
		for(i=1; i<=n; i++)update(tr[i].w,tr[i].w,w[i],1,n,1);
		char op[15];
		for(i=1; i<=q; i++) {
			scanf("%s",op);
			if(op[0]=='I'){
				scanf("%d %d %d",&x,&y,&k);
				add(x,y,k);
			}else if(op[0]=='D'){
				scanf("%d %d %d",&x,&y,&k);
				add(x,y,-k);
			}else{
				scanf("%d",&x);
				printf("%d\n",query(tr[x].w,tr[x].w,1,n,1));
			}
		}
	}
	return 0;
}