操作就是询问某个点的值， 然后就是对一条路径上的值全部修改。

 

最基本的树刨题目了。

树刨的思想：

1. 对于每个点找到他的重儿子。

void dfs1(int o, int u){    sz[u] = 1;    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] + 1;    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,1,n,1);            x = fa[fx]; fx = top[x];        }        else {            Updata(dfn[fy],dfn[y],c,1,n,1);            y = fa[fy]; fy = top[y];        }    }    if(deep[x] < deep[y]) Updata(dfn[x], dfn[y], c, 1, n, 1);    else Updata(dfn[y], dfn[x], c, 1, n,1);}

 

代码：

/*code by: zstu wxktime: 2019/02/22*/#include
      
       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
       
         pll;const int inf = 0x3f3f3f3f;const int _inf = 0xc0c0c0c0;const LL INF = 0x3f3f3f3f3f3f3f3f;const LL _INF = 0xc0c0c0c0c0c0c0c0;const LL mod =  (int)1e9+7;const int N = 2e5 + 100;int n, m, p;int tr[N<<2], lz[N<<2], 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] = 0;    if(l == r){        tr[rt] = a[dto[l]];        return ;    }    int m = l+r >> 1;    Build(lson); Build(rson);    return ;}void PushDown(int rt){    if(lz[rt]){        lz[rt<<1] += lz[rt];        lz[rt<<1|1] += lz[rt];        tr[rt<<1] += lz[rt];        tr[rt<<1|1] += lz[rt];        lz[rt] = 0;    }    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] = 1;    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] + 1;    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 >> 1;    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 >> 1;    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,1,n,1);            x = fa[fx]; fx = top[x];        }        else {            Updata(dfn[fy],dfn[y],c,1,n,1);            y = fa[fy]; fy = top[y];        }    }    if(deep[x] < deep[y]) Updata(dfn[x], dfn[y], c, 1, n, 1);    else Updata(dfn[y], dfn[x], c, 1, n,1);}void init(){    memset(head, -1, sizeof(head));    memset(son, 0, sizeof son);    tot = dtot = 0;}void Ac(){    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);    for(int i = 1,u,v; i < n; ++i){        scanf("%d%d", &u, &v);        add(u, v); add(v, u);    }    dfs1(1,1);    dfs2(1,1,1);    Build(1,n,1);    char op[5];    int x, y, c;    for(int i = 1; i <= p; ++i){        scanf("%s", op);        if(op[0] == 'Q') {            scanf("%d", &x);            printf("%d\n", Query(dfn[x], 1, n, 1));        }        else {            scanf("%d%d%d", &x, &y, &c);            if(op[0] == '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 0;}/*3 2 51 2 32 11 3I 2 3 5Q 27 6 100 0 0 0 0 0 01 22 33 41 55 6I 4 6 1Q 1*/