【题意说明】
给一定棵树，并给定各个点权的值，然后有3种操作：
(1) I C1 C2 K: 把C1与C2的路径上的所有点权值加上K
(2) D C1 C2 K：把C1与C2的路径上的所有点权值减去K
(3) Q C：查询节点编号为C的权值
【问题分析】
典型的树链剖分题目，先进行剖分，然后用线段树去维护即可。
【参考代码】
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define lson k<<1
#define rson k<<1|1
#define lt(i) tree[i].left
#define rt(i) tree[i].right
#define nm(i) tree[i].num
#define tp(i) node[i].top
#define dp(i) node[i].deep
#define fa(i) node[i].father
#define sz(i) node[i].size
#define sn(i) node[i].son
#define id(i) node[i].index
#define hd(i) node[i].head
#define to(i) edge[i].to
#define nx(i) edge[i].next
#define vl(i) node[i].value
const int maxN=50010;
struct Tree{
int left, right, num;
}tree[maxN<<2];
struct Node{
int top, father, deep, size,
index, head, son, value;
}node[maxN];
struct Edge{
int to, next;
}edge[maxN<<1];
int n, m, q, total;
bool init();
void work();
void addedge(int, int, int);
void dfs1(int, int);
void dfs2(int, int);
void build(int, int, int);
void update(int, int, int, int);
int query(int, int);
void solve(int, int, int);
void pushdown(int);
int main(){
while(init()) work();
return 0;
}
bool init(){
if(scanf("%d%d%d",
&n, &m, &q)==EOF) return false;
memset(tree, 0, sizeof(tree));
memset(edge, 0, sizeof(edge));
memset(node, 0, sizeof(node));
total=0;
for(int i=1; i<=n; i++)
scanf("%d", &vl(i));
for(int i=1; i<=m; i++){
int x, y;
scanf("%d%d",
&x, &y);
addedge(x, y, i);
addedge(y, x, i+n);
}
dfs1(1, 1);
dfs2(1, 1);
return true;
}
void addedge(int x, int y, int k){
to(k)=y; nx(k)=hd(x); hd(x)=k;
}
void dfs1(int k, int _dp){
sz(k)=1; dp(k)=_dp;
for(int i=hd(k); i; i=nx(i)){
if(sz(to(i))) continue;
fa(to(i))=k;
dfs1(to(i), _dp+1);
sz(k)+=sz(to(i));
if(sz(sn(k))<sz(to(i)))
sn(k)=to(i);
}
}
void dfs2(int k, int _tp){
id(k)=++total; tp(k)=_tp;
if(sn(k)) dfs2(sn(k), _tp);
for(int i=hd(k); i; i=nx(i))
if(!id(to(i)))
dfs2(to(i), to(i));
}
void work(){
build(1, 1, n);
for(int i=1; i<=n; i++)
update(1, id(i), id(i),
vl(i));
for(int i=0; i<q; i++){
char ch[10];
int u, v, w;
scanf("%s%d",
ch, &u);
if(ch[0]=='Q')
printf("%d
",
query(1, id(u)));
else {
scanf("%d%d",
&v, &w);
if(ch[0]=='D') w=-w;
solve(u, v,
w);
}
}
}
void build(int k, int l, int r){
lt(k)=l; rt(k)=r;
if(l==r) return;
int mid=(l+r)>>1;
build(lson, l, mid);
if(mid<r) build(rson, mid+1,
r);
}
void solve(int u, int v, int w){
int f1=tp(u), f2=tp(v);
while(f1!=f2){
if(dp(f1)<dp(f2)){
swap(f1, f2);
swap(u, v);
}
update(1, id(f1),
id(u), w);
u=fa(f1); f1=tp(u);
}
if(dp(u)<dp(v)) swap(u, v);
update(1, id(v), id(u), w);
}
void update(int k, int l, int r, int v){
if(l<=lt(k)&&r>=rt(k)){
nm(k)+=v; return;
}
pushdown(k);
if(l<=rt(lson)) update(lson,
l, r, v);
if(r>=lt(rson)) update(rson,
l, r, v);
}
void pushdown(int k){
if(nm(k)){
nm(lson)+=nm(k);
nm(rson)+=nm(k);
nm(k)=0;
}
}
int query(int k, int x){
if(lt(k)==rt(k)) return nm(k);
pushdown(k);
if(x<=rt(lson)) return
query(lson, x);
return query(rson, x);
}