一些定义
重儿子：子节点中 子树深度 最大的节点。
轻儿子：除重儿子外的其它子节点。
重边：从一个点到其重儿子的边。
轻边：从一个点到其轻儿子的边。
重链：若干条相连的重边形成的链。单独的节点也看作重链。
那么，一棵树就可以拆分为若干条极长的重链。
实现与重链剖分类似。
一些性质
1.所有链长度之和是 (O(n)) 级别的。
2.任何一个节点的 (k) 级祖先所在的链的长度大于等于 (k) 。
3.任何一个节点跳到根所跳的次数不会超过 (sqrt{n}) 次。
应用
1
题意即在线求树上 (k) 级祖先。
考虑把 (k) 折半，假设得到的数是 (r) 。
根据上面的第 2 条性质 ， (r) 级祖先所在的重链长度不短于 (r) 。
所以，我们只要预处理出每条重链上的所有点以及链顶的 1~链长 级祖先，
这样，在知道 (r) 级祖先后，即可 (O(1)) 算出 (k) 级祖先。
但是，如果直接这么做，复杂度仍然是 (O(log n)) ,这样的复杂度和倍增一样，还是不够优秀。
接下来，可以发现只要满足 (r>k/2) 即可用上面的做法做。
考虑让 (r=highbit(k)) ， (highbit(k)) 即 (k) 在二进制下最高位所代表的值。
这样，用倍增预处理后，即可得到一个 (O(n log n)-O(1)) 的做法。
2
先考虑一个 (O(n^2)) 的做法。
树形 dp ，
设 (dis(i,j)) 表示 (i) 到 (j) 的距离。
设 (f_{i,j}) 表示满足 (x) 在 (i) 的子树中且 (dis(x,i)=j) 的 (x) 的个数。
设 (g_{i,j}) 表示满足 (x) ， (y) 在 (i) 的子树中且 (dis(lca(x,y),x)=dis(lca(x,y),y)=dis(lca(x,y),i)+j) 的数对 ((x,y)) 的个数。（(x
eq y)）
考虑在扫到点 (i) 时的转移：
(ans+=g_{i,0}) ，
(ans+=sum limits_{x,y in son(i),x
eq y} f_{x,j-1} imes g_{y,j+1}) ,
(g_{i,j}+=sum limits_{x,y in son(i),x
eq y} f_{x,j-1} imes f_{y,j-1}) ,
(g_{i,j}+=sum limits_{x in son(i)} g_{x,j+1}) ,
(f_{i,j}+=sum limits_{x in son(i)} f_{x,j-1}) 。
这些转移画个图就可以理解了，而且并不是重点。
这样直接做可以得到一个 (O(n^3)) 的做法，用前缀和优化即可变成 (O(n^2)) 。
考虑继续优化这个算法。
长链剖分，对于重儿子，直接继承它的值，对于轻儿子，它一定是一条重链的顶端，所以直接暴力往下合并。
这样，算法的复杂度变为 (O(sum) 链长 ()) ，即 (O(n)) 。
可以用指针实现，比较方便。
总结：维护与链长，即深度有关的信息时，可以考虑使用长链剖分优化转移。
3
比较显然的贪心策略：每次找到一条最长的路径，记录答案后把路径上的权值清零。
这个策略可以用长链剖分优化。
令链长为这条链上所有点的权值和。
可以发现，因为重链不重合，其实这个贪心就可以转化为选链长最大的 (k) 条重链。