引入
维护一棵树，支持两种操作
-
改变边权 | 边权
-
询问路径中最大权（或其他）
BF 的期望是 \(O(\log n)\)，但是容易退化成 \(O(n)\)，所以引入树链刨分，这里用轻重链刨分
轻重链刨分
记 \(SIZE_i\) 表示以 \(i\) 为根的子树的节点个数，那么对于 \(x\) 为的子节点 \(y\)，若 \(SIZE_y\) 是 \(x\) 子节点中最大的，则称改边为 ⌈ 重边 ⌋，否则为 ⌈ 轻边 ⌋
我们称全部由重边组成的路径为 ⌈ 重路径 ⌋
那么有如下性质
-
若 \((u,v)\) 是轻边，则 \(SIZE_v\leq SIZE_u/2\)
-
从根到某一点的路径上轻边个数不大于 \(O(\log n)\)
-
每个点到根的路径上不超过 \(O(\log n)\) 个重路径 & 轻边
对于询问，先处理出 \(LCA\)，暴力处理轻边，数据结构维护重边
原理还算好理解，难的是实现和常数，直接按思路写那可是要写不知道多少线段树，空间利用率低（动态数组当我没说），查询起来还要把边分成各种奇奇怪怪得东西，总之非常麻烦，我们考虑将所有线段树合并，具体而言
- 是按遍历顺序（重->轻）将原树重新排号，使得重链的点在区间上连续
这样方便维护，还保证了空间和常数
正常人维护都是先求 \(LCA\) 再修改，但也可以不用，常数的事
注意自己维护的是点权还是边权
复杂度是 \(O(\log n^2)\)
标签：log,剖分,轻边,路径,树链,重边,SIZE From： https://www.cnblogs.com/chelsyqwq/p/17625751.html