自动搬运

查看原文

来自洛谷，原作者为

	Bh_hurter 希望能有洞察一切的第三只眼

搬运于2025-08-24 23:11:45，当前版本为作者最后更新于2025-03-31 22:53:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P11967题解

题目传送门

题外话

关于本蒟蒻没学过最近公共祖先这个知识点但在考场悟破天机，自己弄出来了求最近公共祖先的代码......

题意解析

我们手里会有一棵二叉树（注意我们一开始是不知道根节点的），然后要找这样的一些点，将他们其中任意一个从树上删除后都能保证：

• 删除之后能保证题目给出的所有好点对依然互相联通。
• 删除之后那一个坏点对必然不联通。

答案就是这些点的个数。

题目分析与解决

由于题目没有给出明确的根节点，所以我们可以自己设出来根节点，但要注意这个根节点编号不能太大，避免其在本题数据量较小的测试点中根本不存在。
下图是作者将 $1$ 号点设为根节点时，题目所给样例的图示。

很显然，若想保证 $5$ 与 $4$ ， $5$ 与 $3$ 联通，节点 $1$ ， $3$ ， $4$ ， $5$ 都不能删。
而要使点 $2$ ， $6$ 不联通，可以删的只有 $2$ ， $6$ $3$ 。
综上，能删的只有 $2$ ， $6$ 。

通过上述分析，能发现想要两个点联通，便是能从一个点走到另外一个点。又由于本题给出的图只是二叉树，于是从一个点走到另外一个点的路径只有一条： 从一个点走到两个点的最近公共祖先，然后从最近公共祖先走到另一个点 ！

为了保证好点对互相联通，我们只需找到每个点对的最近公共祖先，把一个点到最近公共祖先，从最近公共祖先到另一个点沿路的点全部打上一层标记 $vis_1$ ，意思是这些点绝对不能删。（包括好点对那俩点！）
然后把坏点对的联通路径找出来，也打上标记 $vis_2$ 。

符合题目要求的点，就是 $vis_1=0$ 且 $vis_2=1$ 的点。

代码解决

• 最近公共祖先如何找？以下是一种思路。

1. 找出第一个点的所有祖先。一层一层往上找时一边做好标记。
2. 找另一个点的所有祖先，当第一次发现这个祖先被标记过时，这便是最近公共祖先了。
3. 时间复杂度 $O(\log{n})$ 。

• 整体代码时间复杂度 $O(a\log{n})$ ，可以通过本题。

稍等，身为初三学子的作者尽快补上符合上述思路的代码，求管理员大大给鄙题解留个位置！