科技：dfn 求 LCA

upd：
2023.09.13 新建

非常好思路，学习自 Alex_Wei。

摘要

使用 st 表维护区间内所有点的 dfn 最小的父节点。
优点是好写、时间空间常数小。

前置约定

\(dfn_{i}\) ：\(i\) 是第几个被访问的点

\(sub_{i}\) ：以 \(i\) 为根的子树

\(LCA\) ：\(\text{LCA}(u,v)\)

原理

1. dfn 的性质： 设 \(dfn_{u}<dfn{v}\)， \(\forall dfn_{i} \in [dfn_{u},dfn_{v}] ,\ i\in sub_{Lca},\ i \ne \text{LCA}(u,v)\) ，即区间内 \(LCA\) 不出现，且任意一个节点都是 \(LCA\) 的子节点 。

2. 由上述性质，易知 \([dfn_{u},dfn_{v}]\) 内至少有一个 \(LCA\) 的直接子节点。

3. 设 \(u,v\) 无祖先关系，考虑维护 “区间内所有点的深度最小的父节点”，即为答案。

4. 当 \(u\) 是 \(v\) 的祖先时，3. 不成立，发现仅需去掉 u 即可满足，并且在该情况下 3. 依然成立。所以查询的 \(dfn\) 区间改为 \([dfn_{u}+1,dfn_{v}]\) 。

5. 发现在 4. 的情况下，\(LCA\) 一定是查询范围内 \(dfn\) 最小的点，所以可以从比较 \(dep\) 转化成比较 \(dfn\) 。

6. 至此，问题变为区间可重的无修改查询，使用 st 表，预处理 \(O(n \log n)\) ，查询为 \(O(1)\) ，空间 \(O(n \log n)\)

7. 当 \(u=v\) 时需要特判。

实现

void dfs(int u,int pa)
{
    dfn[u]=++dc;//dc ： dfn_cnt
    st[dc][0]=pa;
    //…………………………………………………………
}
int get(int u,int v)
{
    return ( dfn[u] < dfn[v] ) ? u : v ;
    //传入父节点，返回 dfn 更小的父节点
}
void Pre()
{
    for(int i=1;i<=__lg(n);i++)
        for(int j=1;j+(1<<i)-1<=n;j++)
            st[j][i] = get( st[ j ][i-1] , st[ j+(1<<(i-1)) ][i-1] );
}
int Lca(int u,int v)
{
    if(u==v)return u;
    if((u=dfn[u)>(v=dfn[v))swap(u,v);
    int d=__lg(v-u);
    return get( st[ u+1 ][d] , st[ v-(1<<d)+1 ][d] );
}