引理 1：若 \(n\) 为偶数，则答案为 \(n\)。
若 \(n\) 是叶子，则显然正确。
若 \(n\) 不是叶子，则将整棵树看做以 \(n\) 为根的有根树，一定可以保证最后一个被删除的是根。
故得证。
下面只考虑 \(n\) 为奇数的情况。叶子的情况是平凡的，故下文中 \(u,v\) 均不为叶子。
引理 2：对于距离为奇数的点对 \((u,v)\)，A 可以保证至少拿到 \(u,v\) 中的一个。
A 和 B 的策略均为每次尽量不让 \(u,v\) 成为叶子。
这时除了链 \(u-v\) 和它们两端的点都是能删掉的点，注意到由于 \(n\) 是奇数，所以可以删掉的点个数是奇数，也就是最后 B 会无法操作。
我们称此类点对为 I 类点对。
引理 3：若整棵树是一条链，那么对于任意不包含端点的点集 \(S\) 满足不包含 I 类点对，B 都可以保证拿走所有 \(S\) 中的点。
考虑使用归纳法，假设对于链长为 \(2\) 到 \(n\) 引理都成立，下证链长为 \(n+1\) 的情况引理成立。
设点集 \(S\) 中最靠近两个链端点的点分别是 \(u,v\)。
A 和 B 的策略仍然为每次尽量不让 \(u,v\) 成为叶子。与引理 2 证明类似地，B 可以拿走 \(u,v\) 中的至少一个。
不妨设 B 拿走了 \(u\)，此时剩余的部分仍是一条链。由于 \(u\in S\) 且 \(S\) 中不存在距离为奇数的点对，所以剩余链的 \(u\) 端端点不在 \(S\) 中。由于 \(u\) 被拿走之前一定是叶子，则根据最优策略 \(v\) 一定不是叶子，故剩余链的 \(v\) 端端点不在 \(S\) 中。所以可以转化为一个链长更短的子问题。
对于归纳的初始条件，在 \(n=2\) 时 \(S\) 只可能为空集，显然成立。
由引理 2 和引理 3 即可得出，答案为所有距离为奇数的点对 \(u,v\) 的 \(\min(u,v)\) 的最大值。下面我们考虑树的情况。
引理 4：对于点对 \((u,v,w)\)，若存在 \(m\) 满足其到 \(u,v,w\) 的距离均为偶数，并且 \(m\) 能将 \(u,v,w\) 分到三个不同连通块中，则 \(A\) 可以保证至少拿到 \(u,v,w\) 中的一个。
证明与引理 2 类似，此处略过。
我们称此类点对为 II 类点对，称 \(m\) 为该点对的中心。
引理 5：对于任意不包含 I 类点对和 II 类点对的集合 \(S\)，B 都可以保证拿走所有 \(S\) 中的点。
证明与引理 3 类似，此处略过。
引理 6：答案只有以下情况：叶子结点；满足 \((n,x)\) 是 I 类点对的 \(x\)；满足 \((x,y,n)\) 是 II 类点对的 \(\min(x,y)\)；满足 \((x,y,z)\) 是以 \(n\) 为中心的 II 类点对的 \(\min(x,y,z)\)。
考虑使用反证法。
若存在满足 \((x,y)\) 是 I 类点对的 \(\min(x,y)\) 更优，则有 \((n,x)\) 和 \((n,y)\) 均不为 I 类点对，分析奇偶性可以推出矛盾。
若存在不在上述范围中的 II 类点对 \((x,y,z)\) 满足 \(\min(x,y,z)\) 更优，则有 \((n,x),(n,y),(n,z),(x,y),(x,z),(y,z)\) 均不为 I 类点对，则必然 \((n,x,y)\) 可以构成 II 类点对，矛盾。
故引理成立。
时间复杂度：\(O(n)\)。
标签：叶子,min,题解,类点,奇数,CF1776M,II,引理 From： https://www.cnblogs.com/Kevin090228/p/17156554.html