P5912 JAS 题解
传送门
题意；找出最浅的点分树。
发现这是一个等价问题：给每个结点一个标号，当两个结点标号相同时，它们的路径上必有严格更小的标号。如果找到了这样一种标号方法，每个结点的标号就是它的深度。
同时我们还可以把每个结点的标号
给出一个贪心构造标号的方法：先让所有叶子为
那我们如何判断一个结点
定义一个结点
子树的溢出的结点构成子树的溢出集合。
显然
然后是这个贪心的证明。
记
两个引理：
-
当
u 填f(s_1\sim s_k) 时，u 子树的溢出集合最小。这里的最小是指如果把集合看作二进制数时最小。后面的集合比大小也是这么定义。 -
当
s_k'\ge s_k ，F(s_1\sim s_{k-1}, s_k')\ge F(s_1\sim s_{k-1},s_k) 。
若这两条引理成立，贪心就能简单证出来：
根据 2，要
而根据 1，填
引理 1 证明：
观察到
记
引理 2 证明：
记
发现若
再简化一下命题，因为引理 2 其实表示了一个单调性质，于是我们可以假设
设
-
情况一，
s_k\cap T 有元素大于w 。因为有交集大于
w ，所以f() 一定大于w 。而F() 为填了f() 的溢出集合，因为f()>w ，比f() 低的位都会变成0 （不再溢出）。但
s_k,s_k'=s_k+1 的区别就是：s_k 的最低位一直到w 的前一位都是1 ，第w 位是0 ；s_k+1 的最低位一直到w 的前一位都是0 ，第w 位都是1 。其他的都一样。但是
f() 把较低位的都变成0 了，所以s_k,s_k'=s_k+1 最终算出来的F 相等。 -
情况二，不满足情况一且
w\in T 。因为
f() 选择的位不能出现在任何儿子的溢出集合，所以f() 选择的位一定在所有儿子的溢出集合中都是0 ，也就等价于T 的位上和s_k(s_k') 的位上都是0 。（t=0=>T=s_1\cup\dots\cup s_{k-1} ）因为
w\in T ，所以T 的第w 位为1 。考虑
f(s_1\sim s_{k-1},s_k)=f(T,s_k) ，因为s_k 第w 位以下都是1 ，第w 位为0 ，所以f(T,s_k) 不能在w 及以下。（第w 位及以下都有非0 的）因此f(T,s_k) 是在第w 位以上找到的第一个T,s_k 都是0 的位。又
T,s_k+1 的第w 位都是1 ，重复了，所以f(T,s_k+1) 必须高于第w 位。所以f(T,s_k+1) 是在第w 位以上找到的第一个T,s_k+1 都是0 的位。因为第
w 位以上s_k,s_k+1 相同。所以这种情况下f(T,s_k)=f(T,s_k+1) 。 -
情况三，不满足情况一且
w\not\in T 。则
T 的第w 位为0 。因为
s_k,T 的第w 位都是0 ，所以f(T,s_k) 就是第w 位，F(T,s_k) 的第w 位以上为T\cup s_k ，第w 位为1 ，第w 位以下为0 。即
F(T,s_k)=(T\cup s_k)+1 。因为
s_k+1 的第w 位为1 ，s_k+1 比第w 位更高的位与s_k 相等。所以F(T,s_k+1) 至少第w 位是1 ，比w 高的位和T\cup s_k 相同。而比w 低的位F(T,s_k) 全是0 ，所以F(T,s_k+1)\ge F(T,s_k) 。
综上，引理 2 也得证了。
所以贪心方法是：每个叶节点都标号
计算溢出集合、找出最低的都是