专栏文章

题解：P11967 [GESP202503 八级] 割裂

SSudoXue
P11967题解参与者 2已保存评论 1

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@mipqtyhe
此快照首次捕获于
2025/12/03 16:26
3 个月前
此快照最后确认于
2025/12/03 16:26
3 个月前
查看原文
更好的阅读体验
考场上花费了 2.52.5 小时，连题都没读懂，悻悻离去。是该提高一下自己的阅读理解能力了。

题意概述

给定一棵 nn 个节点的树，定义了若干个好点对和一个坏点对。要求删除某个节点后：
  • 对于每个好点对，两个端点仍然连通（即删除节点不在它们之间的路径上）。
  • 对于坏点对，删除节点必须位于它们之间的路径上（否则删除后坏点对仍然连通）。
于是问题转化为：统计那些既落在坏点对路径上、又不落在任何好点对关键路径上的节点。

Solution

不难想到利用 Tarjan 离线 LCA 一次性求出所有点对的最近公共祖先，再结合树上差分的方法更新好点对信息，同时标记坏点对路径上的节点，最终统计满足条件的节点。
具体地，对于每个好点对 ⟨u,v⟩\langle u, v \rangle 求出其最近公共祖先 LL，方便在树上差分中减去重复计数。同时也用来求出坏点对的 LCA，以确定坏点对路径上需要标记的节点范围。
使用 DFS 遍历树，在 DFS 中利用并查集维护当前节点的祖先信息：
  • 每访问到一个节点，就将其初始化为自己的祖先。
  • 遍历完子节点后，通过并查集合并子节点，并将父节点更新为该节点的祖先。
  • 对于每个查询，当另一端已经被访问时，即可通过并查集找到当前二者的 LCA。
对于每个好点对 ⟨u,v⟩\langle u, v \rangle：
  • 在 uu 与 vv 上各加 11，
  • 在 LL（二者 LCA）上减 11，
  • 在 LL 的父节点上再减 11（避免重复扣除）。
最后利用后序遍历（或按深度从大到小累加）将这些差分值向上传递，得到每个节点被“好点对路径”覆盖的次数。
不难发现，只有差分值为 00 的节点才不会影响好点对的连通性。
利用坏点对 ⟨bU,bV⟩\langle b_U, b_V \rangle 的 LCA LL，从 bUb_U 到 LL 以及从 bVb_V 到 LL 上的所有节点都标记为“坏”节点。只有这些节点被删除时才能使坏点对断开。 最终遍历所有节点，如果一个节点既被标记为坏节点，又在好点对差分累加中为 00（不在任何好点对的关键路径上），则满足条件，计入答案。
时间复杂度 O(n+a)O(n + a)。差点拿下最优解，对比官方题解跑得飞快。
link

评论

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

正在加载评论...