Luogu6574 [BalticOI 2017] Cat in a tree

题意 ： 给出一棵 个点的树，选出一些点使得两两距离 ，最大化选出的点数。

，时限。

---

大力 DP 并长剖+线段树优化可以无脑地做到 。

然而有比较简洁的贪心做法。

对于一条边 ，假设我们求出 两侧的最优解，然后将 连上。

若一方的两个最浅点为 ，另一方两个最浅点为 ，深度分别 ，不妨设 。

显然有 ，故 。

因此必然有 ，两者不冲突。所有可能的冲突都与 之一有关。

可以证明只可能去除 之一。

具体地，若 有矛盾 ，则 不可能再有矛盾 ，与 矛盾。

---

记 表示 子树内的最优解， 表示最优方案中到 最近点距离的最大值。

合并子树 时：

• 若 ，则

• 若 ，则

  这个 需要说明一下，假设 较小，被舍去。而 方的次大值 必然 ，否则 产生矛盾。

合并完所有子树之后，再判定能否选根节点。

复杂度 。