树上路径求交

panyf · 2021-04-12 23:01:47 · 个人记录

做法：

假设当前要求路径 (a,b) 和 (c,d) 的交。

设 d_x 表示 x 的深度。

先求出 p[4]={lca(a,c),lca(a,d),lca(b,c),lca(b,d)}。

将 p 数组按深度排序，取出深度较大的两个，记为 p0,p1。

若存在交，则 (p0,p1) 即所求。

现在只需要判断路径是否有交。

若 p0\neq p1，则一定有交。

否则若 d_{p0}=\max(d_{lca(a,b)},d_{lca(c,d)})，也有交。

否则路径不相交。

正确性证明：

记 u=lca(a,b),v=lca(c,d)。不妨设 d_u\leq d_v。

那么当路径相交时，v 一定在路径 (a,b) 上。原因：假设 x 是路径交上深度最小的点，若 x\neq v，则 fa_x 也在路径 (a,b) 和 (c,d) 上，矛盾。

先考虑路径有交，可以分为以下两种情况：

1.u=v。如图。

2.u\neq v，则有 p0=v。如图。

容易发现，对于两种情况，p 数组中深度较小的两个都是 u，而深度较大的两个恰好是路径交的两个端点。

然后考虑路径不交，此时也对应两种情况：

1.v 在 u 子树外。则 p 数组中所有数全相等，都等于 lca(u,v)。

2.v 在 u 子树内，但不在路径 (a,b) 上。不妨设 d_{lca(c,a)}\leq d_{lca(c,b)}。则有 lca(c,a)=lca(d,a)=u,lca(c,b)=lca(d,b)=lca(v,b)。

容易发现，对于两种情况，都有 p0=p1，所以当 p0\neq p1 时路径一定相交。

最后还需要考虑 p0=p1 且路径相交的情况，根据最开始证明的结论，当 p0=v 时相交。

习题：P3250 [HNOI2016]网络