题解：P14762 [Opoi 2025] CCD 的长恨歌

SuyctidohanQ · 2025-12-17 21:08:04 · 题解

我们维护若干条虚链，每条虚链上的节点深度递增，且在同一条从根出发的路径上。

对于每个新节点 x（从 2 到 n）：

• 枚举当前所有虚链，检查 x 是否可以加入该链。
• 对于链 j，设链底为 y，计算 p = \operatorname{LCA}(x, y)：
  • 如果 p = y，说明 y 是 x 的祖先，x 可能加入该链。
  • 如果 p = x，说明 x 是 y 的祖先，但这种情况不会发生，因为 x 是新节点。
  • 否则，x 不能加入该链。
• 对于可能加入的链，在链上二分查找 x 应该插入的位置：找到链上深度最大的节点 z 使得 \operatorname{LCA}(x, z) = z，则 x 应插入在 z 之后。
• 如果没有链可以插入 x，或者所有可能链都要求 x 插入在链头，则创建一条新链，以 x 为链头。

构建完所有虚链后，需要确定它们之间的父子关系。对于每条链 i（链底为 x）：

• 枚举其他所有链 j（链底为 y），计算 p = \operatorname{LCA}(x, y)。
• 如果 p 不在链 j 上，则链 j 不可能是链 i 的父链。
• 否则，记录所有这样的 p。这些 p 都在从 x 到根的路径上，其中深度最大的 p 就是链 i 的链头的父亲。

根据构建的链内连接和链间连接，输出所有边。