概述
-
轻重链剖分通过将树剖分为若干条重链和它们之间相连的轻边，将树上路径问题转化成序列问题。
-
具体来讲，有很多树上路径问题本质上是把序列上的问题搬到了树上，此时我们可以进行轻重链剖分（后简记为轻重剖或重剖），将树上路径拆分为多条重链头尾相接，并通过能快速维护重链信息的数据结构来求解。
-
重剖方式如下：
-
定义重儿子为所有儿子中 \(siz\) 最大的一个。
-
规定到重儿子的边为重边，其余为轻边，称连续的重边构成的链为重链。
-
实际实现中一般还没完。将重儿子换到最前面，把树拍扁成 dfn 序，对其建立线段树，于是重链总是连续的一段，子树也总是连续的一段。
-
-
重剖的优越性在于树上任意点到根的路径上至多有 \(O(\log)\) 条重链，这也代表着只会有 \(O(\log)\) 条轻边。证明如下：
-
由重儿子 \(siz\) 最大，每次走轻边（记为从 \(now\) 到 \(fa\)）时至少和一个不比 \(now\) 轻的节点共子树了。
-
故每走一次轻边，所在子树的 \(siz\) 至少翻倍，至多翻倍 \(O(\log)\) 次。这和启发式合并的复杂度证明有异曲同工之妙，我有时也称重剖的剖分方式为“启发式分裂”。
-
-
p.s.重剖也可以用来求 lca，毕竟求树上路径的形式就是一个找 lca 的过程，但这么做未免太小题大做。
例题
P3384 【模板】重链剖分/树链剖分
-
题意：路径加，路径求和，子树加，子树求和。
-
即板子，由 dfn 序上重链和子树的连续性，易解。
P1505 [国家集训队] 旅游
-
题意略。大概算是树剖板子的集大成者。
-
首先对于树上边权问题，我们的一般处理方法是边权下放，即构建外向树然后把信息存在终点上。不能建对偶图，因为那很可能不是树。
-
然后比较有趣的操作就是取相反数，注意细节别写挂就好，显然还可以支持路径加、子树加、子树和、子树最值等等，但那样的话实现起来就更恶心了。
P2486 [SDOI2011] 染色
- 题意略。利用类似最大子段和的方式维护即可。
P2680 [NOIP2015 提高组] 运输计划
-
题意略。
-
不妨预处理出所有路径的长度，然后二分答案。
-
对每条路径，如果其过长，则对路径上的边 \(+1\)。
-
最后检验是否存在一条边，使得其的覆盖次数恰为不合法路径条数，且将其改为 \(0\) 权边后最长的不合法路径也合法了即可。
-
鉴于树剖多一只 \(\log\)，考虑 lca+树上差分实现。