arc116E
题意
题解
答案显然具有单调性。
二分，对于 \(mid\) 我们计算最少需要几个点使得可以全部覆盖整个树。
我们有一个显然的贪心，对于以 \(u\) 为跟的子树，我们选 \(u\) 当且仅当子树内最深的到 \(u\) 的距离恰好为 \(mid\)。
如何证明？
考虑如果不是这样，我们找到最深的一个选的 \(u\) 不满足上述贪心策略。
跳 \(u\) 父亲，显然 \(fa_u\) 不劣于 \(u\)。
考虑 \(fa_u\) 能更多照顾到 \(u\) 子树外的点，而且此时 \(u\) 子树内依旧合法。
有了贪心策略就很简单了。
我们维护 \(a_u\) 表示 \(u\) 子树内所选的点还能支持多远。
\(b_u\) 表示 \(u\) 子树内不能被覆盖到的点距离 \(u\) 的距离。注意 \(u\) 距离 \(u\) 0个距离。
考虑 \(\min_{(u,v)}{a_v-1}\) 和 \(\min_{(u,v)}b_v+1\) 关系即可。
记 \(p=\min_{(u,v)}a_v-1,q=\min_{(u,v)}b_v+1\)
如果 \(p\geq q\) 证明 \(u\) 子树内不能被覆盖的点可以通过其他所选点覆盖。
此时 \(b_u=-1\),\(a_u=p\)
否则如果 \(p=mid\) 代表必须采取行动选 \(u\) 覆盖，此时 \(b_u=-1,a_u=mid\)。
否则，我们不覆盖，但是此时所选点也不会在产生贡献，所以我们可以直接 \(a_u=0,b_u=q\)。
吐槽
at 的题解很奇怪，不是很懂为什么要提到
dynamic programming,也不解释 贪心策略。
这个贪心策略还是很明显的，但是正确性确实需要考虑，而我已经想到这个贪心，但是看到题解没提到贪心，而是放了一个
dynamic programming 就觉得自己错了。
希望这篇博客能帮到你吧。