P5290 [十二省联考 2019] 春节十二响 题解

先考虑一条链的情况。此时有两类形态：

• $1$ 号结点是链的一个端点。
• $1$ 号结点在链的中部。

第一类情况是简单的，显然任意两个点之间都有祖先关系，直接把所有点都单独划组，答案即为所有点的代价的和。

第二类情况就是合并两个链，链内所有元素还是单个分组，而两条链之间则可以两两分组。配对方式使用数学归纳 + Exchange-Argument trick 可以发现一定是让最大的组分别配对，剩下若干个元素单个配对最优。一遍排序即可做到 $O(n\log n)$。

考虑扩展到树上。$O(n^2\log n)$ 做法是简单的，直接在每个点上开一个堆记录当前点子树内所有组的代价，然后按照上面的贪心策略暴力合并即可。

此时注意到这个东西和合并的顺序无关，因此想到用启发式合并来优化，时间复杂度变为 $O(n\log^2n)$，可以轻松通过。