[luoguP3258] [JLOI2014]松鼠的新家（lca + 树上差分）

传送门

需要把一条路径上除了终点外的所有数都 + 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

上一篇：[bzoj1787][Ahoi2008]Meet 紧急集合（lca）

下一篇：[luoguP3178] [HAOI2015]树上操作（dfs序 + 线段树 || 树链剖分）

---

lca 差分 倍增