操作就是询问某个点的值， 然后就是对一条路径上的值全部修改。
最基本的树刨题目了。
树刨的思想：
1. 对于每个点找到他的重儿子。
void dfs1(int o, int u){
sz[u] = ;
for(int i = head[u]; ~i; i = nt[i]){
int v = to[i];
if(v == o) continue;
dfs1(u, v);
if(sz[v] > sz[son[u]]) son[u] = v;
sz[u] += sz[v];
}
}
2.求DFS序。对于每个节点记录下dfs序，他的父节点，他的祖先节点（也就是这条重链上最高的节点），这个点对应线段树的位置，线段树对应到节点的位置。
在DFS的过程中，先搜重儿子，然后再搜轻儿子，这样可以保证一条重链在线段树中是连续的，故可以用线段树区间修改。
void dfs2(int o, int u, int t){
deep[u] = deep[o] + ;
top[u] = t;
fa[u] = o;
dfn[u] = ++dtot;
dto[dtot] = u;
if(son[u]) dfs2(u, son[u], t);
for(int i = head[u]; ~i; i = nt[i]){
int v = to[i];
if(v == o || v == son[u]) continue;
dfs2(u, v, v);
}
}
3. 接下来就是对路径的修改。
假如我们需要修改 u -- v 这条路径。
那么我们先令fu = top[u], fv = top[v], 如果不相等，则将深度大的往上跳，跳的时候完成你要的操作。
相等之后就说明在一条链上了， 这个时候完成操作后就可以退出了。
注意的是， 判断的是 fu 和 fv 的深度 而不是 u v 的深度。
void Updata_Path(int x, int y, int c){
int fx = top[x], fy = top[y];
while(fx != fy){
if(deep[fx] > deep[fy]){
Updata(dfn[fx],dfn[x],c,,n,);
x = fa[fx]; fx = top[x];
}
else {
Updata(dfn[fy],dfn[y],c,,n,);
y = fa[fy]; fy = top[y];
}
}
if(deep[x] < deep[y]) Updata(dfn[x], dfn[y], c, , n, );
else Updata(dfn[y], dfn[x], c, , n,);
}
代码：
/*
code by: zstu wxk
time: 2019/02/22
*/
#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lch(x) tr[x].son[0]
#define rch(x) tr[x].son[1]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int inf = 0x3f3f3f3f;
const int _inf = 0xc0c0c0c0;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL _INF = 0xc0c0c0c0c0c0c0c0;
const LL mod = (int)1e9+;
const int N = 2e5 + ;
int n, m, p;
int tr[N<<], lz[N<<], a[N];
int head[N], nt[N], to[N], tot;
int sz[N], son[N];
int top[N], fa[N], dfn[N], dto[N], deep[N], dtot;
void Build(int l, int r, int rt){
lz[rt] = tr[rt] = ;
if(l == r){
tr[rt] = a[dto[l]];
return ;
}
int m = l+r >> ;
Build(lson); Build(rson);
return ;
}
void PushDown(int rt){
if(lz[rt]){
lz[rt<<] += lz[rt];
lz[rt<<|] += lz[rt];
tr[rt<<] += lz[rt];
tr[rt<<|] += lz[rt];
lz[rt] = ;
}
return ;
}
void add(int u, int v){
to[tot] = v;
nt[tot] = head[u];
head[u] = tot++;
}
void dfs1(int o, int u){
sz[u] = ;
for(int i = head[u]; ~i; i = nt[i]){
int v = to[i];
if(v == o) continue;
dfs1(u, v);
if(sz[v] > sz[son[u]]) son[u] = v;
sz[u] += sz[v];
}
}
void dfs2(int o, int u, int t){
deep[u] = deep[o] + ;
top[u] = t;
fa[u] = o;
dfn[u] = ++dtot;
dto[dtot] = u;
if(son[u]) dfs2(u, son[u], t);
for(int i = head[u]; ~i; i = nt[i]){
int v = to[i];
if(v == o || v == son[u]) continue;
dfs2(u, v, v);
}
}
int Query(int x, int l, int r, int rt){
if(l == r)
return tr[rt];
int m = l+r >> ;
PushDown(rt);
if(x <= m) return Query(x, lson);
return Query(x, rson);
}
void Updata(int L, int R, int C, int l, int r, int rt){
// cout << L << " l with r " << r << endl;
if(L <= l && r <= R){
lz[rt] += C;
tr[rt] += C;
return ;
}
int m = l+r >> ;
PushDown(rt);
if(L <= m) Updata(L, R, C, lson);
if(m < R) Updata(L, R, C, rson);
return ;
}
void Updata_Path(int x, int y, int c){
int fx = top[x], fy = top[y];
while(fx != fy){
if(deep[fx] > deep[fy]){
Updata(dfn[fx],dfn[x],c,,n,);
x = fa[fx]; fx = top[x];
}
else {
Updata(dfn[fy],dfn[y],c,,n,);
y = fa[fy]; fy = top[y];
}
}
if(deep[x] < deep[y]) Updata(dfn[x], dfn[y], c, , n, );
else Updata(dfn[y], dfn[x], c, , n,);
}
void init(){
memset(head, -, sizeof(head));
memset(son, , sizeof son);
tot = dtot = ;
}
void Ac(){
for(int i = ; i <= n; ++i) scanf("%d", &a[i]);
for(int i = ,u,v; i < n; ++i){
scanf("%d%d", &u, &v);
add(u, v); add(v, u);
}
dfs1(,);
dfs2(,,);
Build(,n,);
char op[];
int x, y, c;
for(int i = ; i <= p; ++i){
scanf("%s", op);
if(op[] == 'Q') {
scanf("%d", &x);
printf("%d\n", Query(dfn[x], , n, ));
}
else {
scanf("%d%d%d", &x, &y, &c);
if(op[] == 'D') c = -c;
Updata_Path(x,y,c);
// Tdfs(1,n,1);
}
}
}
int main(){
while(~scanf("%d%d%d", &n, &m, &p)){
init();
Ac();
}
return ;
}
/*
3 2 5
1 2 3
2 1
1 3
I 2 3 5
Q 2 7 6 10
0 0 0 0 0 0 0
1 2
2 3
3 4
1 5
5 6
I 4 6 1
Q 1 */