题意：
给出一棵树，每个顶点上有一个权值。
操作：选择一条路径，并将路径上所有的点的权值同时加或减某个数。
查询：某个点的当前权值
分析：
树链剖分完毕后，就是简单的线段树区间更新。
提交的时候注意要要加一句扩栈的代码，用C++提交。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 void read(int& x) { 7 x = 0; 8 char c = ' '; 9 while(c < '0' || c > '9') c = getchar(); 10 while('0' <= c && c <= '9') { 11 x = x * 10 + c - '0'; 12 c = getchar(); 13 } 14 } 15 16 const int maxn = 50000 + 10; 17 const int maxnode = maxn * 4; 18 19 struct Edge 20 { 21 int v, nxt; 22 Edge() {} 23 Edge(int v, int nxt) :v(v), nxt(nxt) {} 24 }; 25 26 int n, m, q; 27 int a[maxn]; 28 29 int ecnt, head[maxn]; 30 Edge edges[maxn * 2]; 31 32 void AddEdge(int u, int v) { 33 edges[++ecnt] = Edge(v, head[u]); 34 head[u] = ecnt; 35 edges[++ecnt] = Edge(u, head[v]); 36 head[v] = ecnt; 37 } 38 39 int dep[maxn], fa[maxn], son[maxn], sz[maxn]; 40 41 int tot, id[maxn], pos[maxn], top[maxn]; 42 43 void dfs(int u) { 44 sz[u] = 1; son[u] = -1; 45 for(int i = head[u]; i; i = edges[i].nxt) { 46 int v = edges[i].v; 47 if(v == fa[u]) continue; 48 fa[v] = u; 49 dep[v] = dep[u] + 1; 50 dfs(v); 51 sz[u] += sz[v]; 52 if(son[u] == -1 || sz[v] > sz[son[u]]) son[u] = v; 53 } 54 } 55 56 void dfs2(int u, int tp) { 57 top[u] = tp; 58 id[u] = ++tot; 59 pos[tot] = u; 60 if(son[u] == -1) return; 61 if(son[u]) dfs2(son[u], tp); 62 for(int i = head[u]; i; i = edges[i].nxt) { 63 int v = edges[i].v; 64 if(v == fa[u] || v == son[u]) continue; 65 dfs2(v, v); 66 } 67 } 68 69 int sumv[maxnode], addv[maxnode]; 70 char cmd[10]; 71 72 void pushup(int o) { sumv[o] = sumv[o<<1] + sumv[o<<1|1]; } 73 74 void build(int o, int L, int R) { 75 if(L == R) { sumv[o] = a[pos[L]]; return; } 76 int M = (L + R) / 2; 77 build(o<<1, L, M); 78 build(o<<1|1, M+1, R); 79 pushup(o); 80 } 81 82 void pushdown(int o, int L, int R) { 83 if(addv[o]) { 84 addv[o<<1] += addv[o]; 85 addv[o<<1|1] += addv[o]; 86 int M = (L + R) / 2; 87 sumv[o<<1] += (M - L + 1) * addv[o]; 88 sumv[o<<1|1] += (R - M) * addv[o]; 89 addv[o] = 0; 90 } 91 } 92 93 void update(int o, int L, int R, int qL, int qR, int v) { 94 if(qL <= L && R <= qR) { 95 sumv[o] += (R - L + 1) * v; 96 addv[o] += v; 97 return; 98 } 99 pushdown(o, L, R); 100 int M = (L + R) / 2; 101 if(qL <= M) update(o<<1, L, M, qL, qR, v); 102 if(qR > M) update(o<<1|1, M+1, R, qL, qR, v); 103 pushup(o); 104 } 105 106 void UPDATE(int u, int v, int val) { 107 int t1 = top[u], t2 = top[v]; 108 while(t1 != t2) { 109 if(dep[t1] < dep[t2]) { swap(u, v); swap(t1, t2); } 110 update(1, 1, n, id[t1], id[u], val); 111 u = fa[t1]; t1 = top[u]; 112 } 113 if(dep[u] > dep[v]) swap(u, v); 114 update(1, 1, n, id[u], id[v], val); 115 } 116 117 int query(int o, int L, int R, int p) { 118 if(L == R) return sumv[o]; 119 pushdown(o, L, R); 120 int M = (L + R) / 2; 121 if(p <= M) return query(o<<1, L, M, p); 122 else return query(o<<1|1, M+1, R, p); 123 } 124 125 int main() 126 { 127 while(scanf("%d%d%d", &n, &m, &q) == 3) { 128 for(int i = 1; i <= n; i++) read(a[i]); 129 130 memset(head, 0, sizeof(head)); 131 ecnt = 0; 132 for(int i = 1; i < n; i++) { 133 int u, v; read(u); read(v); 134 AddEdge(u, v); 135 } 136 137 dfs(1); 138 tot = 0; 139 dfs2(1, 1); 140 141 memset(addv, 0, sizeof(addv)); 142 build(1, 1, n); 143 144 while(q--) { 145 scanf("%s", cmd); 146 int u, v, d; 147 read(u); 148 if(cmd[0] == 'Q') { 149 printf("%d ", query(1, 1, n, id[u])); 150 } else { 151 read(v); read(d); 152 if(cmd[0] == 'D') d = -d; 153 UPDATE(u, v, d); 154 } 155 } 156 } 157 158 return 0; 159 }