传送门
需要把一条路径上除了终点外的所有数都 + 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 17 18 inline void add(int x, int y) 19 24 25 inline void swap(int &x, int &y) 26 27 inline void dfs(int u) 28 37 } 38 39 inline int lca(int x, int y) 40 52 53 inline void dfs1(int u) 54 61 } 62 int main() 64 76 dfs(1); 77 for(i = 2; i <= n; i++) 78 85 dfs1(1); 86 for(i = 1; i <= n; i++) printf("%d\n", val[i]); 87 return 0; 88 }View Code
上一篇：[POJ2446] Chessboard（二分图最大匹配-匈牙利算法）
下一篇：[luoguP2564][SCOI2009]生日礼物（队列）
lca 倍增 差分
