长剖的本质是一种贪心。（启发式合并本质也是类似哈夫曼树的过程） 在此题中，首先肯定变直径，然后选端点为根。然后选叶子。而每个叶子为了不重复计算，可以只计算其长剖后所在链的贡献。（本题精髓，用长剖来贪心） 然后钦定某个点必选，就是一种反悔贪心。很显然的思路是删掉排名 2 ∗ k − 1 2*k-1 2∗k−1 的叶子，但考虑： 所以需要考虑离其最近被选的点 #include<bits

长剖的本质是一种贪心。（启发式合并本质也是类似哈夫曼树的过程） 在此题中，首先肯定变直径，然后选端点为根。然后选叶子。而每个叶子为了不重复计算，可以只计算其长剖后所在链的贡献。（本题精髓，用长剖来贪心） 然后钦定某个点必选，就是一种反悔贪心。很显然的思路是删掉排名 2 ∗ k − 1 2*k-1 2∗k−1 的叶子，但考虑： 所以需要考虑离其最近被选的点 #include<bits