树分块

在树上的 \(\log\) 数据结构一般都要求维护的信息有较好的性质。正如序列就有一些问题只能用分块这种两个暴力拼起来的算法解决，分块也可以搬到树上。

在树上跑一遍从下往上的贪心，使得每个节点只需要跳不超过 \(B\) 次 fa 就可以到达一个关键点，只需要放置不超过 \(\frac{n}{B}\) 个关键点。取 \(B=n^{?}\)，此时关键点的数量和到关键点的距离都很短，可以实现很多暴力。