P9369

我们可以发现每个点集要么是一个链，要么是不同子树中的许多点。 那么显然，如果我们想要取一个链作为集合，那么只有把这个链一直取到叶子才是最优的。 那么我们考虑把这棵树做长链剖分，假设我们得到了 p 条长链，每条长链的长度为 lp_i。 假设我们一开始全都用第二类集合来划分，那么答案显然是整棵树最大的深 ......