[ARC205D] Non-Ancestor Matching 题解

赛时没打这场 ABC。

设 的重儿子是 ，以 为根的子树为 ， 的大小是 ， 中最多能选出 个点对。定义点 是好的，当且仅当 。接下来分点 是不是好的分类讨论：

• 若点 是好的：显然有 。
• 若点 不是好的：我们尝试让 成为好的。具体地，我们可以在 中先选取一些点对，并且从 中删去这些点，使得 减小，从而使点 成为好的。在 中最多可以选取 个点对，所以 的最小值是 。若 ，则说明我们可以让 成为好的，；否则 ，含义显然。

答案是 ，时间复杂度 。

提交记录。