题解：P9601 [IOI 2023] 最长路程

SegTree · 2025-11-15 14:54:55 · 题解

容易注意到的是，图一定可以被划分为两条链。

归纳进行，假设现在有两条链 a 和 b，当前插入结点。

• 若 b 为空，则将新点插入 b；
• 若 a 的末尾能插入或者 b 的末尾能插入，则直接插入。
• 否则，a 的末尾与 b 的末尾一定有边，那么把 b 倒过来接 a 后头，然后将 b 设置为新点。

此时就得到了两条链。则若 a 的链尾与 b 有边：

• 若 a 的链头与 b 有边或者 a 的链尾与 b 有边，都可以直接拼上；
• 否则，a 的链头与 a 的链尾有边，a 为环，可以在任意位置断开，还是可以直接拼。

同理，判掉 b 的链尾与 a 有边的情形，此时 a 和 b 都是环，那么：

• 若 a 和 b 之间无边，直接取较长的。
• 否则，a 和 b 都可以在任意处断开，找到这条边即可。

用二分来寻找边，并对「归纳进行」部分进行模拟，可以做到 2n+2\log_2 n 次。

考虑优化，发现需要在 3 次操作内加入 2 个点。一个非确定性做法是，以 \dfrac{1}{2} 的概率选择先问 a 还是先问 b，但是由于有多测，不能通过。考虑确定性做法：先问 i 和 i+1 有没有边，要是有边只需要分别询问 a,b 的链尾能否拼 i；否则，一个链尾在 i 和 i+1 中至少有一个能连。都可以做到 3 次确定 2 个点。

这样就做到了确定性 1.5n+2\log_2 n 次。