CF1292C Xenon's Attack on the Gangs

题意：给出一棵 个节点的树，你需要给每条边分配互不相同的 以内的权值，使得所有 条路径边权集合的 总和最大。输出这个最大值。

，时限 。

---

• 引理 1：若边权 不在一条路径上，则不可能存在一条路径的 是 。

因此，我们可以按照 的顺序放置，当前放置的边要成为一条链。如果链延伸不下去了就乱放，这时没有贡献。

• 引理 2：考虑最后产生贡献的链，这条链的边权一定是单谷的。

  证明：如果不是单谷的，设 是单谷的，而 第一次违反这个性质。将 向着谷底交换可以使 总和变大。

该引理说明，在填写 时，一定要紧接着填在 形成的链的两端。每新填写一条边，答案增加两侧子树大小的乘积。

---

考虑 DP。

设 表示当前链的两个端头分别为 时，已经得到的收益得最大值。

是以 为根时 的子树大小。 是以 为根时 的父亲。它们容易 次 预处理。

考虑目前最大的数字放在哪一端，有如下转移

记忆化搜索即可。边界为 。答案是 ，总复杂度 。