树上路径交问题

在一棵有 $n$ 个节点的树上给出一路径 $(u_i,v_i)$ 的集合。现求一些路径的交集。

分析

这个东西可以转化为 LCA 问题。

记两条路径为 $a:(p_a,q_a), b:(p_b,q_b)$，它们的交集首先也是一条路径或空。

两两求解 $a,b$ 端点的 LCA。

1. 若 $b$ 在 $a$ 端点的 LCA 一侧，即 $b$ 的 LCA 在 $a$ 的 LCA 之下。那么 $a$ 与 $b$ 的 LCA 显然有两个（$b$ 与 $a$ 在 LCA 另一侧的端点）等于 $f(p_a,p_b)$。剩余两个 LCA 结果就是路径交。注意判断路径交为空的特殊情况，此时按前述方法求得的交也有一个节点，且在 $a$ 上。
2. 若 $b$ 跨过 $a$ 的 LCA。$a$ 和 $b$ 的 LCA 同样也有两个相同，路径交依然以另外两 LCA 为端点。路径交不可能为空。

所以最终的结论就是从两路径的 4 个 LCA 中取两个不相同的结果作为路径交的端点；当结果两两相同时路径交可能为空或退化为 1 个点。

路径交的计算继承自集合交运算，满足交换律和结合律。所以如上操作可以使用能维护区间信息的数据结构，如线段树。

例题

摸了。