P14211 [ROI 2016 Day2] 快递服务

29 分的简单解法：$O(nk^2)$

• 考虑每对路径 $P_1, P_2$。
• 使用深度优先搜索找到第一条路径上的顶点。
• 使用同样的搜索找到第二条路径上的顶点。
• 路径交集的长度等于两条路径上共同顶点的数量减一。

简单解法的 64 倍加速

• 预先为每条路径使用深度优先搜索找到其上的顶点集。
• 考虑每对路径 $P_1, P_2$。
• 需要找到两个集合的交集大小——这可以通过位压缩来完成。
• 可以使用 <bitset>。

简单解法的概念性加速

• 为每条路径预先找到其上的顶点集。
• 对于每个顶点，存储所有经过它的路径。
• 问题的答案是一条路径，遍历其一个端点，设为顶点 $v$。
• 将树以选定的顶点 $v$ 为根。
• 对于每条经过 $v$ 的路径，将其端点标记为“特殊的”。
• 对于每个子树，计算其中的特殊顶点数量。
• 需要选择最深的顶点，其子树中至少有两个特殊顶点。
• 这样，解法的第一部分时间复杂度为 $O(nm)$。
• 第二部分需要从每个顶点开始进行深度优先搜索，因此时间复杂度为 $O(n^2)$。
• 总的渐进复杂度为 $O(n(n+m))$。
• 得分：41 分。

快速路径相交（LCA）

• 遍历路径对，然后快速找到交集长度。
• 每条路径可以分解为两条垂直路径：为此，需要能够找到最近公共祖先 (LCA)。
• 垂直路径的相交：
  • 找到下端点的 LCA，如果它们相交，这将是相交的最低点。
  • 垂直路径相交的最高点将是原始路径的上端点中较低的那个。
• 复杂度分析：
  • 使用倍增算法可以在 $O(\log n)$ 内找到 LCA。
  • 总的解法复杂度为 $O(n \log n + m^2 \log n)$。
  • 得分：48 分。
  • 使用欧拉序和 ST 表可以在 $O(1)$ 内找到 LCA。
  • 解法复杂度现在是 $O(n \log n + m^2)$。
  • 得分：56 分。

“自下而上”解法

• 假设我们固定了相交的最低点。
• 那么，在经过这个顶点的路径中，我们只对那两条尽可能向上延伸的路径感兴趣。
• 这可以通过常规的深度优先搜索来维护。

$O(mh \log n)$ 解法

• 对于每个顶点，存储经过它的路径列表。
• 遍历路径相交的一个端点，设为顶点 $v$。
• 按进入时间对经过该顶点的路径端点进行排序。
• 现在遍历一条经过顶点 $v$ 的路径，并考虑其端点。
• 为了选择第二条路径，我们注意到有趣的候选者是按进入时间最接近的两个路径端点。

完整解法

• 启动一个深度优先搜索，它将返回在此子树中开始但在其外部某处结束的路径的端点。
• 同时，路径的端点将按进入时间排序：需要一个 set。
• 为了实现这个深度优先搜索，需要合并子节点的集合。
• 当合并两个集合时，我们将使用将较小集合的元素移动到较大集合的方法（启发式合并）。
• 在移动一个元素的过程中，考虑已经存在于集合中的按进入时间最接近的两个路径端点，并尝试更新答案。
• 一切都非常简单！ 有问题吗？