图论

1. 树上简单路径

树上简单路径 \((u,v)\) 的关键是 LCA。具体而言，通过端点的 LCA 节点 \(p\)，可以将 \((u,v)\) 拆分为两条祖先-后代链 \((u,p)\)，\((v,p)\)，利于处理。以下讨论的路径均为简单路径。

1.1 基础

LCA 若干种求法：

1. 暴力跳父亲

2. 倍增

3. 重链剖分

4. 通过 dfs 序转成 RMQ

5. 通过欧拉序转成 加减 1RMQ（当然也可以转成普通 RMQ）

路径 \((u,v)\) 之间的距离（边权）：\(d_u+d_v-2d_{\text{LCA(u,v)}}\)。（\(d_u\) 为点 \(u\) 到树根的距离）。

路径 \((u,v)\) 之间点权和：\(d_u+d_v-d_{\text{LCA(u,v)}}-d_{fa_{\text{LCA(u,v)}}}\)。（\(d_u\) 为点 \(u\) 到树根的点权和）。

1.2 判断点是否在路径上

两种方法。设判断 \(p\) 是否在 \((u,v)\) 上。

1. 通过距离判定：若 \(p\) 在 \((u,v)\) 上，则一定满足 \(\text{dis}(u,p)+\text{dis}(p,v)=\text{dis}(u,v)\)。其中 \(\text{dis(x,y)}\) 表示 \(x,y\) 之间的边的数量。

2. 通过位置关系判定：

   首先考虑祖先-后代链，若 \(p\) 不在路径的端点上，则其中一个端点在 \(p\) 的子树内，另一端点在 \(p\) 的子树外。

   对于非祖先后代链也是类似的，将其拆分成两条祖先后代链，特判 \(p\) 在 LCA、\(u\)、\(v\) 处的情况后，和祖先-后代链做法一致。

1.3 两条路径

主要讨论两条路径的交。这里的交定义为两条路径的公共点集。

1.3.1 判断两条路径是否相交

引理：两条路径相交，则其中一条路径的 LCA 一定在另一条路径上。

首先考虑两条祖先-后代链的相交情况 \((a,b),(c,d)\)（其中 \(a\) 为 \(b\) 的祖先，\(c\) 为 \(d\) 的祖先），则 \(a\) 在 \((c,d)\) 上或 \(c\) 在 \((a,b)\) 上。

将其余情况转成上述情况。即满足 \(\text{lca}(a,b)\) 在 \((c,d)\) 上或 \(\text{lca}(c,d)\) 在 \((a,b)\) 上。

1.3.2 两条路径相交部分长度

同 1.3.1 类似地考虑两条祖先-后代链。若两条路径有交，则靠下的端点为 \(\text{lca(b,d)}\)，靠上的端点为 \(a,b\) 中深度较大的节点。

将其余路径拆成祖先-后代链，分别计算相交的长度。由于拆分成的祖先-后代链无公共边，所以相交部分长度不会算重。