题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3966
#include<bits/stdc++.h>
using namespace std;
const int maxn =1e5+5;
/*
题目大意:就是在一颗树上维护，
两点间路径的权重修改，查询单点权值.对于树上路径的维护和修改，
树链剖分的话最重要的还是一种分块的思想，
把链分成重轻链，然后把点映射到树状数组中，
再单独封装修改操作，这样修改的复杂度就被均摊了。
代码太模板了，看看就好，我压缩和注释的感觉还可以。
*/
///链式前向星存边
struct edge{int u,nxt;}e[maxn<<1];
int head[maxn],tot;
void init(){memset(head,-1,sizeof(head));tot=0;}
void add(int x,int y){e[tot]=edge{y,head[x]};head[x]=tot++;}
///两遍DFS，第一遍确定各个数组，第二遍哈希边
int siz[maxn],dep[maxn],fa[maxn],son[maxn];
void dfs1(int u,int pre,int d)
{siz[u]=1,fa[u]=pre,dep[u]=d;for(int i=head[u];~i;i=e[i].nxt){int v=e[i].u;if(v==pre) continue;dfs1(v,u,d+1);siz[u]+=siz[v];if(son[u]==-1||siz[v]>siz[son[u]]) son[u]=v;}
}
///重新建立映射，方便丢到数据结构中
int p[maxn],fp[maxn],top[maxn];///双射
void dfs2(int u,int sp)
{top[u]=sp,p[u]=tot++,fp[p[u]]=u;///建立双射，建立父节点if(son[u]==-1) return ;dfs2(son[u],sp);///建立链的关系for(int i=head[u];~i;i=e[i].nxt){int v=e[i].u;if(v!=son[u]&&v!=fa[u]) dfs2(v,v);}
}
///树状数组数据结构维护树上操作
int bit[maxn<<1];
int lowbit(int x){return x&(-x);}
void refresh(int x,int d){for(;x<maxn;bit[x]+=d,x+=lowbit(x));}
int sum(int x){int ret=0;for(;x>0;ret+=bit[x],x-=lowbit(x));return ret;}
///读入数据域
int n,m,q,x,y,z;
int v[maxn];
char op[10];
///修改路径上的权重
void update(int u,int v,int val)
{int f1=top[u],f2=top[v];while(f1!=f2){if(dep[f1]<dep[f2]){swap(f1,f2);swap(u,v);}refresh(p[u]+1,-val),refresh(p[f1],val);u=fa[f1],f1=top[u];}if(dep[u]>dep[v]) swap(u,v);refresh(p[u],val),refresh(p[v]+1,-val);
}int main()
{while(scanf("%d%d%d",&n,&m,&q)!=EOF){init();///初始化for(int i=1;i<=n;i++) scanf("%d",&v[i]);for(int i=0;i<m;i++){scanf("%d%d",&x,&y);add(x,y),add(y,x);}memset(son,-1,sizeof(son));///又重新初始化memset(bit,0,sizeof(bit));tot=1;dfs1(1,-1,0),dfs2(1,1);for(int i=1;i<=n;i++) refresh(p[i],v[i]),refresh(p[i]+1,-v[i]);for(int i=0;i<q;i++){scanf("%s",op);if(op[0]=='Q'){scanf("%d",&x);printf("%d\n",sum(p[x]));}else{scanf("%d%d%d",&x,&y,&z);if(op[0]=='D') z=-z;update(x,y,z);}}}return 0;
}