思路 ：树链剖分就是可以把一个路径上的点映射成几段连续的区间上。这样对于连续的区间可以用线段树维护，
对于每一段连续的区间都可以通过top [ ]数组很快的找到这段连续区间的头。跳的过程类似于 lca ，但这里 要注意的是
每一个点只属于一条链。 (重载运算符时要注意 node 一个 新的结点，不要 乱用*this 指针)
#include<bits/stdc++.h>
using namespace std;
#define MID int m = (l+r)/2
#define maxn 56789
#define inf 0x3f3f3f3f
struct node
{
int sum,lazy,cnt;
node()
{
sum=lazy=cnt=0;
}
node operator+(const node &a)const
{
node ret;
ret.sum=a.sum+sum;
ret.cnt=a.cnt+cnt;
return ret;
}
} tree[maxn*4];
char str[12];
vector<int>edge[maxn];
int data[maxn],n,m,id[maxn],fa[maxn],u,ans;
int son[maxn],top[maxn],tid[maxn],cnt,v,ad;
int deep[maxn],siz[maxn],id_data[maxn],q;
void pushdown(int root)
{
if(tree[root].lazy==0)return ;
tree[root*2].lazy+=tree[root].lazy;
tree[root*2+1].lazy+=tree[root].lazy;
tree[root*2].sum+=tree[root*2].cnt*tree[root].lazy;
tree[root*2+1].sum+=tree[root*2+1].cnt*tree[root].lazy;
tree[root].lazy=0;
}
void bulid(int root,int l,int r)
{
tree[root].lazy=0;
if(l==r)
{
tree[root].sum=id_data[l];
tree[root].cnt=1;
return ;
}
MID;
bulid(root*2,l,m);
bulid(root*2+1,m+1,r);
tree[root]=tree[root*2]+tree[root*2+1];
}
void updata(int root,int l,int r,int L,int R,int ad)
{
if(r<L||l>R)return;
if(L<=l&&r<=R)
{
tree[root].sum+=tree[root].cnt*ad;
tree[root].lazy+=ad;
return ;
}
pushdown(root);
MID;
updata(root*2,l,m,L,R,ad);
updata(root*2+1,m+1,r,L,R,ad);
tree[root]=tree[root*2]+tree[root*2+1];
}
void query(int root,int l,int r,int L,int R)
{
if(r<L||l>R)return ;
if(L<=l&&r<=R)
{
ans+=tree[root].sum;
return;
}
pushdown(root);
MID;
query(root*2,l,m,L,R);
query(root*2+1,m+1,r,L,R);
}
void dfs1(int u,int pre,int ide)
{
son[u]=-1,siz[u]=1;
deep[u]=ide,fa[u]=pre;
for(int i=0; i<edge[u].size(); i++)
{
int v=edge[u][i];
if(v==pre)continue;
dfs1(v,u,ide+1);
if(son[u]==-1||siz[son[u]]<siz[v])
son[u]=v;
}
}
void dfs2(int u,int tp)
{
top[u]=tp, tid[u]=++cnt;
id_data[cnt]=data[u];
if(son[u]!=-1)dfs2(son[u],tp);
for(int i=0; i<edge[u].size(); i++)
{
int v=edge[u][i];
if(v==fa[u]||v==son[u])continue;
dfs2(v,v);
}
}
void solve(int x,int y,int ad)
{
int tx=top[x],ty=top[y];
while(tx!=ty)
{
if(deep[tx]<deep[ty])swap(x,y),swap(tx,ty);
updata(1,1,n,tid[tx],tid[x],ad);
x=fa[tx],tx=top[x];
}
if(deep[x]<deep[y])swap(x,y);
updata(1,1,n,tid[y],tid[x],ad);
}
int main()
{
while(~scanf("%d%d%d",&n,&m,&q))
{
cnt=0;
for(int i=1; i<=n; i++)
{
scanf("%d",&data[i]);
edge[i].clear();
}
while(m--)
{
scanf("%d%d",&u,&v);
edge[u].push_back(v);
edge[v].push_back(u);
}
dfs1(1,0,1);
dfs2(1,1);
bulid(1,1,n);
while(q--)
{
scanf("%s",str);
if(str[0]=='I')
{
scanf("%d%d%d",&u,&v,&ad);
solve(u,v,ad);
}
else if(str[0]=='D')
{
scanf("%d%d%d",&u,&v,&ad);
solve(u,v,-ad);
}
else
{
scanf("%d",&u);
ans=0;
query(1,1,n,tid[u],tid[u]);
printf("%d\n",ans);
}
}
}
return 0;
}