首先看上去像差分约束，但边太多不太对。
假如一个点标 $x$，距离它 $d$ 的点可能标 $x-d$（如果 $x>d$），否则只能标 $x+d$。
这样是不是只需要考虑一个点对应的约束就做完了？但事实上（根据三角形不等式）其他约束几乎从来不会被自动满足（除非是链）。
绝对值。前两天做的题中就有绝对值。绝对值对应到距离。那么设法把树拍平到数轴上。
按照 DFS 序给树上节点标号？不太对。欧拉序？对完了。考虑将每个点的标号设为它在欧拉序中第一次出现的位置。
随手写一发哦哦过不了样例啊。有点麻烦，欧拉序一定是合法的，但未必是最优的。
我需要枚举每个点作为根吗？复杂度太高。怎么办？
注意到根的标号一定是 1。那么，考虑标号最大的节点，它是在欧拉序中最后出现的节点。我们要尽可能把它往前排。
也就是说，最小化它前面的“冗余”（那些在退出一个点时产生的记录）的节点数。
冗余的节点数……注意到我们可以挑一条（起点为根的）路径不产生冗余节点数，这时我们遍历的最后一个点是这条路径的终点。而其他地方必然产生冗余记录。
那么挑选直径作为这条路径。大胆写一发，发现 AC 了。
不过为什么这是对的？首先我们的构造能够达到 $2n-l$，其中 $l$ 是树的直径的长度（点数）。
能不能更优？答案是否定的。如何证明呢？
考虑将所有点按标号大小升序排序。我们假想进行一次遍历：从标号最小的点开始，每次沿两点间唯一简单路径走到下一个点，直到标号最大的点结束。
我们记 $d_i$ 是遍历到第 $i$ 个（意味着标号第 $i$ 大）点时已经走过的距离（边数），$p_i$ 是第 $i$ 个点，$a_i$ 是第 $i$ 个点的标号。
注意到 $d_{i+1} - d_i = \operatorname{dis}(p_{i+1}, p_i) \leq a_{i+1}-a_i$，即标号之差不小于距离。
注意到让第 $i$ 个点标号为 $d_i+1$（加一是为了让所有点标号不小于 1）时，每个不等号都可以取等。由于 $a_1$ 不变，取等显然更优。
并且取等的情况同样都可以建模为一种遍历顺序。
那么考虑最优化遍历顺序。
优化目标是 $d_n$，即总共经过的边的数目。
使用一种拆贡献的方法：考虑每条边被经过了多少次。
每条边被经过两次是显然上界。
那么考虑让尽可能多的边只被遍历一次。
注意到遍历一次就像“过桥”，如果从这条边砍断后的两个联通分量中的一个到了另一个，就无法再回去了。
显然所有遍历一次的边形成了一条链（这可以用归纳法证明）。
最大化它们的数目就是最大化链的长度。
不妨取直径作为这条链。
注意到只遍历一次的边的数目不可能更多，即不会因为有边走了超过两次而增加。
所以剩下的边一定遍历两次。
注意到这时答案等于 $2n-l$，与我们的构造一致。于是证毕。
代码：
| |