需要把一条路径上除了终点外的所有数都 + 1，
比如，给路径 s - t 上的权值 + 1，可以先求 x = lca(s，t)
类似数列上差分的思路，可以给 s 和 f[t] 的权值 + 1，给 x 和 f[x] 的权值 - 1
最后统计以每个节点为根的子树的和，则每个节点的权值就是子树的权值。
——代码
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 5 const int MAXN = 300001; 6 int n, cnt; 7 int a[MAXN], head[MAXN], to[MAXN << 1], next[MAXN << 1], deep[MAXN], f[MAXN][21], val[MAXN]; 8 9 inline int read() 10 { 11 int x = 0, f = 1; 12 char c = getchar(); 13 for(; !isdigit(c); c = getchar()) if(c == '-') f = -1; 14 for(; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0'; 15 return x * f; 16 } 17 18 inline void add(int x, int y) 19 { 20 to[cnt] = y; 21 next[cnt] = head[x]; 22 head[x] = cnt++; 23 } 24 25 inline void swap(int &x, int &y) { x ^= y ^= x ^= y; } 26 27 inline void dfs(int u) 28 { 29 int i, v; 30 deep[u] = deep[f[u][0]] + 1; 31 for(i = 0; f[u][i]; i++) f[u][i + 1] = f[f[u][i]][i]; 32 for(i = head[u]; i != -1; i = next[i]) 33 { 34 v = to[i]; 35 if(!deep[v]) f[v][0] = u, dfs(v); 36 } 37 } 38 39 inline int lca(int x, int y) 40 { 41 int i; 42 if(deep[x] < deep[y]) swap(x, y); 43 for(i = 20; i >= 0; i--) 44 if(deep[f[x][i]] >= deep[y]) 45 x = f[x][i]; 46 if(x == y) return x; 47 for(i = 20; i >= 0; i--) 48 if(f[x][i] != f[y][i]) 49 x = f[x][i], y = f[y][i]; 50 return f[x][0]; 51 } 52 53 inline void dfs1(int u) 54 { 55 int i, v; 56 for(i = head[u]; i != -1; i = next[i]) 57 { 58 v = to[i]; 59 if(v != f[u][0]) dfs1(v), val[u] += val[v]; 60 } 61 } 62 63 int main() 64 { 65 int i, x, y, z; 66 n = read(); 67 memset(head, -1, sizeof(head)); 68 for(i = 1; i <= n; i++) a[i] = read(); 69 for(i = 1; i < n; i++) 70 { 71 x = read(); 72 y = read(); 73 add(x, y); 74 add(y, x); 75 } 76 dfs(1); 77 for(i = 2; i <= n; i++) 78 { 79 x = a[i - 1]; 80 y = a[i]; 81 z = lca(x, y); 82 val[z]--, val[f[z][0]]--; 83 val[x]++, val[f[y][0]]++; 84 } 85 dfs1(1); 86 for(i = 1; i <= n; i++) printf("%d ", val[i]); 87 return 0; 88 }