专栏文章

题解：P11967 [GESP202503 八级] 割裂

BBh_hurter
P11967题解参与者 15已保存评论 26

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
26 条
当前快照
1 份
快照标识符
@mipqzw9u
此快照首次捕获于
2025/12/03 16:31
3 个月前
此快照最后确认于
2025/12/03 16:31
3 个月前
查看原文

P11967题解

题目传送门

题外话

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

题意解析

我们手里会有一棵二叉树（注意我们一开始是不知道根节点的），然后要找这样的一些点，将他们其中任意一个从树上删除后都能保证：
  • 删除之后能保证题目给出的所有好点对依然互相联通。
  • 删除之后那一个坏点对必然不联通。
答案就是这些点的个数。

题目分析与解决

由于题目没有给出明确的根节点，所以我们可以自己设出来根节点，但要注意这个根节点编号不能太大，避免其在本题数据量较小的测试点中根本不存在。
下图是作者将 11 号点设为根节点时，题目所给样例的图示。
很显然，若想保证 55 与 44 ， 55 与 33 联通，节点 11 ， 33 ， 44 ， 55 都不能删。
而要使点 22 ， 66 不联通，可以删的只有 22 ， 66 33 。
综上，能删的只有 22 ， 66 。
通过上述分析，能发现想要两个点联通，便是能从一个点走到另外一个点。又由于本题给出的图只是二叉树，于是从一个点走到另外一个点的路径只有一条： 从一个点走到两个点的最近公共祖先，然后从最近公共祖先走到另一个点 ！
为了保证好点对互相联通，我们只需找到每个点对的最近公共祖先，把一个点到最近公共祖先，从最近公共祖先到另一个点沿路的点全部打上一层标记 vis1vis_1 ，意思是这些点绝对不能删。（包括好点对那俩点！）
然后把坏点对的联通路径找出来，也打上标记 vis2vis_2 。
符合题目要求的点，就是 vis1=0vis_1=0 且 vis2=1vis_2=1 的点。

代码解决

  • 最近公共祖先如何找？以下是一种思路。
  1. 找出第一个点的所有祖先。一层一层往上找时一边做好标记。
  2. 找另一个点的所有祖先，当第一次发现这个祖先被标记过时，这便是最近公共祖先了。
  3. 时间复杂度 O(log⁡n)O(\log{n}) 。
  • 整体代码时间复杂度 O(alog⁡n)O(a\log{n}) ，可以通过本题。
稍等，身为初三学子的作者尽快补上符合上述思路的代码，求管理员大大给鄙题解留个位置！

评论

共 26 条评论，欢迎与作者交流。

正在加载评论...