题意：给一棵树，要求你对一个路径上的值进行加减，查询某个点的值

思路：重链剖分。

由于分了轻重儿子，我每次到重儿子的top只要O(1)，经过的轻儿子最多logn条，那么我每次往上跳最多跳logn次。

所以总的路径可以分为：dfn[top[u]]到dfn[u]组成的完整路径，每次更新完走向fa[top[u]]防止重复操作。

参考：某大哥博客

代码：

#include
#include
#include

int aa[maxn];
int n, m;
struct Edge{
int v, next;
}edge[maxn << 1]; int head[maxn], tot; void init(){ memset(head, -1, sizeof(head)); tot = tol = 0; memset(son, -1, sizeof(son)); } void addEdge(int u, int v){ edge[tot].v = v; edge[tot].next = head[u]; head[u] = tot++; } void dfs1(int u, int pre, int d){ deep[u] = d; fa[u] = pre; sz[u] = 1; for(int i = head[u]; i != -1; i = edge[i].next){ int v = edge[i].v; if(v == pre) continue; dfs1(v, u, d + 1); sz[u] += sz[v]; if(son[u] == -1 || sz[v] > sz[son[u]])
son[u] = v;
}
}
void dfs2(int u, int tp){ //得到top
top[u] = tp;
dfn[u] = ++tol;
fd[tol] = u;
if(son[u] == -1) return;
dfs2(son[u], tp);
for(int i = head[u]; i != -1; i = edge[i].next){
int v = edge[i].v;
if(v != son[u] && v != fa[u]){
dfs2(v, v);
}
}
}

int sum[maxn << 2], lazy[maxn << 2]; void build(int l, int r, int rt){ if(l == r){ sum[rt] = aa[fd[l]]; lazy[rt] = 0; return; } lazy[rt] = 0; int m = (l + r) >> 1;
build(l, m, rt << 1); build(m + 1, r, rt << 1 | 1); sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; } void pushdown(int rt, int l, int r){ int m = (l + r) >> 1;
if(lazy[rt]){
lazy[rt << 1] += lazy[rt]; lazy[rt << 1 | 1] += lazy[rt]; sum[rt << 1] += lazy[rt] * (m - l + 1); sum[rt << 1 | 1] += lazy[rt] * (r - m); lazy[rt] = 0; } } void update(int l, int r, int L, int R, int v, int rt){ if(L <= l && R >= r){
lazy[rt] += v;
sum[rt] += v * (r - l + 1);
return;
}
pushdown(rt, l, r);
int m = (l + r) >> 1;
if(L <= m) update(l, m, L, R, v, rt << 1); if(R > m)
update(m + 1, r, L, R, v, rt << 1 | 1); sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; } int query(int pos, int l, int r, int rt){ if(l == r){ return sum[rt]; } pushdown(rt, l, r); int m = (l + r) >> 1;
if(pos <= m)
return query(pos, l, m, rt << 1);
else
return query(pos, m + 1, r, rt << 1 | 1);
}

void add(int u, int v, int val){
while(top[u] != top[v]){
if(deep[top[u]] < deep[top[v]]) swap(u, v); update(1, n, dfn[top[u]], dfn[u], val, 1); u = fa[top[u]]; } if(deep[u] > deep[v]) swap(u, v);
update(1, n, dfn[u], dfn[v], val, 1);
}

int main(){
int Q;
while(~scanf("%d%d%d", &n, &m, &Q)){
init();
for(int i = 1; i <= n; i++){
scanf("%d", &aa[i]);
}
for(int i = 0; i < m; i++){
int u, v;
scanf("%d%d", &u, &v);
addEdge(u, v);
addEdge(v, u);
}
dfs1(1, -1, 0);
dfs2(1, 1);
build(1, n, 1);
while(Q--){
char o[2];
int a, b, c;
scanf("%s", o);
if(o[0] == 'I'){
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
else if(o[0] == 'D'){
scanf("%d%d%d", &a, &b, &c);
add(a, b, -c);
}
else{
scanf("%d", &a);
printf("%d\n", query(dfn[a], 1, n, 1));
}
}
}
return 0;
}