题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3966
树链剖分的模版，成段更新单点查询。熟悉线段树的成段更新的话就小case啦。
//树链剖分 边权修改 单点查询
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int MAXN = 5e4 + ;
struct data {
int to , next;
}edge[MAXN << ];
int head[MAXN] , cnt , tot;
int top[MAXN] , par[MAXN] , son[MAXN] , size[MAXN] , dep[MAXN];
int id[MAXN] , fid[MAXN]; //id[i]表示i对应在线段树上的位置 fid[i]表示线段树位置是i的叶子 对应的节点
int a[MAXN]; void init() {
tot = cnt = ;
memset(head , - , sizeof(head));
} inline void add(int u , int v) {
edge[tot].next = head[u];
edge[tot].to = v;
head[u] = tot++;
} void dfs1(int u , int p , int d) {
dep[u] = d , size[u] = , son[u] = u , par[u] = p;
for(int i = head[u] ; ~i ; i = edge[i].next) {
int v = edge[i].to;
if(v == p)
continue;
dfs1(v , u , d + );
if(size[v] >= size[son[u]] || son[u] == u)
son[u] = v;
size[u] += size[v];
}
} void dfs2(int u , int p , int t) {
top[u] = t , id[u] = ++cnt;
fid[cnt] = u;
if(son[u] != u)
dfs2(son[u] , u , t);
for(int i = head[u] ; ~i ; i = edge[i].next) {
int v = edge[i].to;
if(v == p || v == son[u])
continue;
dfs2(v , u , v);
}
} struct segtree {
int l , r;
int sum;
}T[MAXN << ]; void pushup(int p) {
if(T[p].sum != ) {
int ls = p << , rs = (p << )|;
T[ls].sum += T[p].sum;
T[rs].sum += T[p].sum;
T[p].sum = ;
}
} void build(int p , int l , int r) {
int mid = (l + r) >> ;
T[p].l = l , T[p].r = r;
T[p].sum = ;
if(l == r) {
T[p].sum = a[fid[l]]; //
return ;
}
build(p << , l , mid);
build((p << )| , mid + , r);
} void updata(int p , int l , int r , int num) {
int mid = (T[p].l + T[p].r) >> ;
if(T[p].l == l && T[p].r == r) {
T[p].sum += num;
return ;
}
pushup(p);
if(r <= mid) {
updata(p << , l , r , num);
}
else if(l > mid) {
updata((p << )| , l , r , num);
}
else {
updata(p << , l , mid , num);
updata((p << )| , mid + , r , num);
}
} int query(int p , int pos) {
int mid = (T[p].l + T[p].r) >> ;
if(T[p].l == T[p].r && T[p].r == pos) {
return T[p].sum;
}
pushup(p);
if(pos <= mid) {
return query(p << , pos);
}
else {
return query((p << )| , pos);
}
} void change(int u , int v , int num) {
int fu = top[u] , fv = top[v];
int sum = ;
while(fu != fv) {
if(dep[fu] > dep[fv]) {
updata( , id[fu] , id[u] , num);
u = par[fu];
fu = top[u];
}
else {
updata( , id[fv] , id[v] , num);
v = par[fv];
fv = top[v];
}
}
if(dep[u] >= dep[v]) {
updata( , id[v] , id[u] , num);
}
else {
updata( , id[u] , id[v] , num);
}
} int main()
{
int n , u , v , m , xx;
while(~scanf("%d %d %d" , &n , &xx , &m)) {
init();
for(int i = ; i <= n ; ++i) {
scanf("%d" , a + i);
}
for(int i = ; i < n ; ++i) {
scanf("%d %d" , &u , &v);
add(u , v);
add(v , u);
}
cnt = ;
dfs1( , , );
dfs2( , , );
build( , , cnt);
char q[];
while(m--) {
scanf("%s" , q);
if(q[] == 'Q') {
scanf("%d" , &xx);
printf("%d\n" , query( , id[xx]));
}
else if(q[] == 'I') {
scanf("%d %d %d" , &u , &v , &xx);
change(u , v , xx);
}
else {
scanf("%d %d %d" , &u , &v , &xx);
change(u , v , -xx);
}
}
}
return ;
}