解题思路

本题概括起来有两种操作：

1. 更新路径上点权
2. 查询点权

树链剖分之后用线段树处理区间更新和单点查询即可（用树状数组应该会更简单一些）。

参考代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1

const int INF = 0x3f3f3f3f;
const int MAXN = 50001;

struct edge {
    int to;
    int next;
} e[MAXN<<1];

int n, m, p, a, b, k, w[MAXN], val[MAXN];
int fa[MAXN], dep[MAXN], sz[MAXN], son[MAXN];
int idx, id[MAXN], top[MAXN];
int head[MAXN], cnt;
int SUM[MAXN<<2], lazy[MAXN<<2];;
char op[2];

void Add(int u, int v) {
    e[cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt++;
}

void DFS1(int u, int pre, int d) {
    dep[u] = d;
    sz[u] = 1;
    son[u] = 0;
    fa[u] = pre;
    for(int i=head[u]; ~i; i=e[i].next) {
        int v = e[i].to;
        if(v != pre) {
            DFS1(v, u, d+1);
            sz[u] += sz[v];
            if(sz[v] > sz[son[u]])
                son[u] = v;
        }
    }
}

void DFS2(int u, int t) {
    top[u] = t;
    id[u] = ++idx;
    if(son[u]) DFS2(son[u], t);
    for(int i=head[u]; ~i; i=e[i].next) {
        int v = e[i].to;
        if(v!=fa[u] && v!=son[u])
            DFS2(v, v);
    }
}

void PushUp(int rt) {
    SUM[rt] = SUM[rt<<1] + SUM[rt<<1|1];
}

void PushDown(int rt, int m) {
    if(lazy[rt]) {
        lazy[rt<<1] += lazy[rt];
        lazy[rt<<1|1] += lazy[rt];
        SUM[rt<<1] += lazy[rt] * (m - (m >> 1));
        SUM[rt<<1|1] += lazy[rt] * (m >> 1);
        lazy[rt] = 0;
    }
}

void Build(int l, int r, int rt) {
    lazy[rt] = 0;
    if(l == r) {
        SUM[rt] = val[l];
        return;
    }
    int m = (l + r) >> 1;
    Build(lson);
    Build(rson);
    PushUp(rt);
}

void Update(int L, int R, int v, int l, int r, int rt) {
    if(L<=l && r<=R) {
        lazy[rt] += v;
        SUM[rt] += v * (r - l + 1);
        return;
    }
    PushDown(rt, r-l+1);
    int m = (l + r) >> 1;
    if(L <= m) Update(L, R, v, lson);
    if(R > m) Update(L, R, v, rson);
    PushUp(rt);
}

int Query(int L, int R, int l, int r, int rt) {
    if(L<=l && r<=R) return SUM[rt];
    PushDown(rt, r-l+1);
    int m = (l + r) >> 1;
    int ret = 0;
    if(L <= m) ret += Query(L, R, lson);
    if(R > m) ret += Query(L, R, rson);

    return ret;
}

void UpdatePath(int u, int v, int value) {
    while(top[u] != top[v]) {
        if(dep[top[u]] < dep[top[v]])
            swap(u, v);
        Update(id[top[u]], id[u], value, 1, n, 1);
        u = fa[top[u]];
    }
    if(dep[u] > dep[v]) swap(u, v);
    Update(id[u], id[v], value, 1, n, 1);
}

int main(int argc, char const *argv[]) {
    while(~ scanf("%d %d %d", &n, &m, &p)) {
        memset(head, -1, sizeof head);
        cnt = 0;
        for(int i=1; i<=n; ++i) {
            scanf("%d", &w[i]);
        }
        for(int i=1; i<=n-1; ++i) {
            scanf("%d %d", &a, &b);
            Add(a, b);
            Add(b, a);
        }
        idx = 0;
        DFS1(1, -1, 1);
        DFS2(1, 1);
        for(int i=1; i<=n; ++i) {
            val[id[i]] = w[i];
        }
        Build(1, n, 1);
        while(p--) {
            scanf("%s", op);
            if(op[0] == 'I') {
                scanf("%d %d %d", &a, &b, &k);
                UpdatePath(a, b, k);
            }
            if(op[0] == 'D') {
                scanf("%d %d %d", &a, &b, &k);
                UpdatePath(a, b, -k);
            }
            if(op[0] == 'Q') {
                scanf("%d", &a);
                printf("%d\n", Query(id[a], id[a], 1, n, 1));
            }
        }
    }
    
    return 0;
}