题解：P11967 [GESP202503 八级] 割裂

SudoXue · 2025-04-01 17:31:33 · 题解

更好的阅读体验

考场上花费了 2.5 小时，连题都没读懂，悻悻离去。是该提高一下自己的阅读理解能力了。

题意概述

给定一棵 n 个节点的树，定义了若干个好点对和一个坏点对。要求删除某个节点后：

• 对于每个好点对，两个端点仍然连通（即删除节点不在它们之间的路径上）。
• 对于坏点对，删除节点必须位于它们之间的路径上（否则删除后坏点对仍然连通）。

于是问题转化为：统计那些既落在坏点对路径上、又不落在任何好点对关键路径上的节点。

Solution

不难想到利用 Tarjan 离线 LCA 一次性求出所有点对的最近公共祖先，再结合树上差分的方法更新好点对信息，同时标记坏点对路径上的节点，最终统计满足条件的节点。

具体地，对于每个好点对 \langle u, v \rangle 求出其最近公共祖先 L，方便在树上差分中减去重复计数。同时也用来求出坏点对的 LCA，以确定坏点对路径上需要标记的节点范围。

使用 DFS 遍历树，在 DFS 中利用并查集维护当前节点的祖先信息：

• 每访问到一个节点，就将其初始化为自己的祖先。
• 遍历完子节点后，通过并查集合并子节点，并将父节点更新为该节点的祖先。
• 对于每个查询，当另一端已经被访问时，即可通过并查集找到当前二者的 LCA。

对于每个好点对 \langle u, v \rangle：

• 在 u 与 v 上各加 1，
• 在 L（二者 LCA）上减 1，
• 在 L 的父节点上再减 1（避免重复扣除）。

最后利用后序遍历（或按深度从大到小累加）将这些差分值向上传递，得到每个节点被“好点对路径”覆盖的次数。

不难发现，只有差分值为 0 的节点才不会影响好点对的连通性。

利用坏点对 \langle b_U, b_V \rangle 的 LCA L，从 b_U 到 L 以及从 b_V 到 L 上的所有节点都标记为“坏”节点。只有这些节点被删除时才能使坏点对断开。 最终遍历所有节点，如果一个节点既被标记为坏节点，又在好点对差分累加中为 0（不在任何好点对的关键路径上），则满足条件，计入答案。

时间复杂度 O(n + a)。差点拿下最优解，对比官方题解跑得飞快。

link