题解：P11967 [GESP202503 八级] 割裂

Bh_hurter · 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}) ，可以通过本题。

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