现在两篇题解一篇是直接告诉你贪心，另一篇是“正确性显然”。感觉 AGC 题题解这种情况很常见啊，直接丢上来一个玄妙做法，正确性谈都不谈。我发这种贴子好像也经常是 AGC 题。

官方题解给了一个非常漂亮的证明：假设我们不使用二进制维护集合，而使用 $d$ 进制，其中 $d$ 是一个大于 $n$ 的整数。

即，如果我们已经确定了 $u$ 子树内点的标号，记 $f_u$ 为 $\sum_kd^k$，其中 $k$ 满足 $u$ 的子树里存在一个标号为 $k$ 的节点，并且它到 $u$ 的路径上没有标号比 $k$ 大的点。

那么，如果我们贪心地决定 $u$ 的标号，那么实际上是让 $f_u$ 为最小的，大于 $u$ 的儿子的 $f$ 值和的，$d$ 进制表示内只有 $0$ 和 $1$ 的整数。我们实际上只需要最小化 $f_1$，所以贪心是正确的。

应该也可以写一个大力调整的证法出来跟上面这个证法等价，不过这不重要。

说起来好像很多题解没写证明的题官方题解都写了，那我要说外国人写的题解就是比中国人牛逼，你们可以骂我罕见了！