ARC117D Miracle Tree

题意 ： 给出一棵 个节点的树，要求给每个节点赋予权值 ，满足下列条件。

• 对于点 ，。
• 满足上述两个条件的情况下， 的最大值最小。

构造一种方案。

，时限 。

---

• 性质 ： 将点按照 从大到小排序为 ，则第二条要求可以改写为 ：

  因为对于 有 ，所以能确保其他点对成立。

对于一个给定的 ，为了使得 的最大值最小，我们令

中的最大值即为 。

问题转化为：找一个排列 ，使得 最小。

若在树上走一个环路，则长度总为 。

选取直径端点作为起点和终点，若直径长度为 （点数）则长度为 。

• 另一种思路

首先不难想到用欧拉序中的 来作为 。

（根据树上莫队的正确性）该构造显然合法，但不一定最优。

考虑从直径的某一段开始 ，而从另一端结束，这样能使得最大的 最小。

具体地，若直径长度为 （点数），最大的 为 。

复杂度 。