LCA（Lowest Common Ancestor) 最近公共祖先 Luogu P3379

①倍增算法

倍增算法是最经典的求LCA的算法。

dep[u]存储u的深度

fa[u][i]存储从u点向上跳$2^i$层的祖先节点。$i = 0,1,2,3… …$

即u点向上跳$1,2,4,8… …$层的祖先

点的标号从 $1$ 到 $n$ , $0$号点为边界。
1. dfs创建st表
倍增递推： fa[u][i] = fa[fa[u][i - 1]][i - 1](原理为$2^{i - 1}+2^{i - 1} = 2^i $ )

void dfs(int u,int father){
    dep[u] = dep[father] + 1; // 标记深度
    fa[u][0] = father; // 向上跳2^0层就是直接与u点相邻的祖先

    for(int i = 1; i <= 19; ++i){ // 题目中给到N最大到5e5，要预留足够的层数空间给结点
    // 可以先写个程序求出 （1 << i） >= N的第一个i值
        fa[u][i] = fa[fa[u][i - 1]][i - 1]; // 倍增递推
    }

    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if(j == father)continue;
        dfs(j,u);
    }
}

2.利用st表求lca

1. 设u为u,v中深度较大的那一个，先将u点跳到与v点同一深度
2. 将u,v一起向上跳，一直跳到lca的下一层。

int lca(int u,int v){
    if(dep[u] < dep[v])swap(u,v); // 保证u是深度较大的哪一个

    for(int i = 19; i >= 0 ; --i){
        if(dep[fa[u][i]] >= dep[v])u = fa[u][i]; // 将u一直向上跳直到跳到v的同一层
    }
    if(u == v)return u; // 可能存在这种情况：v就是u的祖先，那么v就是u,v的lca

    for(int i = 19; i >= 0; --i){
        if(fa[u][i] != fa[v][i]){
            u = fa[u][i], v = fa[v][i]; // 这里u和v一定可以跳跃到lca的刚好下一层邻接层
        }
    }
    return fa[u][0]; // 由于u在lca的下一层，因此我们只需要再向上取2^0层就是lca了
}

lca函数中的if判断是怎样限制u和v的跳跃的呢？

假设我们需要向上跳的层数为 $n$ ,

我们可以将整数 $n$ 通过一个二进制串来表示。

而我们的每一次跳跃都减掉了 $n$ 中最高位的1。

当循环到二进制串中为0的位，假设我们将这一位减1，也就是由u跳到fa[u][i],会导致 $n$

减到负数，也就是u会跳到恰好 $lca$ 或者 $lca $ 上方。此时fa[u][i] == fa[v][i]。 ($lca$及以上全是$u,v$的公共

祖先)。由于代码中的if(fa[u][i] != fa[v][i])，此时 $u,v$ 是不会往上跳的。这个条件会一直限制 $u,v$

在 $lca$ 的下方。

②Tarjan算法 $O(n + m)$

下面u表示当前结点，v表示u的子节点
1. 从根开始深搜，入u时打标记vis[u] = true;
2. 枚举u的儿子v，遍历完v的子树，回到u时再把v指向u p[v] = u;
3. 遍历完u的所有儿子后，离u时枚举所有以u为起点的查询，如果终点被搜过，那么u,v的lca就是 p[v];
4. 递归遍历完整棵树得到全部答案。

int find(int x){
    return x == p[x]?x:p[x] = find(p[x]);
}

void tarjan(int u){
    vis[u] = true;

    for(int i = h[u]; i != -1; i = ne[i]){ 
        int j = e[i];
        if(!vis[j]){
            tarjan(j);
            p[j] = u; // 回时指父
        }
    }

    for(auto q: query[u]){ // 离时搜根，这里query是一个PII类型的vector，第一维存储查询终点，第二维存储查询编号
        int v = q.first, i = q.second;
        if(vis[v])ans[i] = find(v);
    }
}

代码中需要注意的细节问题：

1. 要在回到u之后再更新才能保证find(v)找到的是lca,不然全部查询到根节点去了。
2. 存查询时要存两次，即u,v：query[u].push_back({v,i}),query[v].push_back({u,i});因为我们无法判断u和v哪一个先被标记。

③树链剖分 $O(n + mlogn)$

首先来了解一些概念：

重儿子:父结点的所有儿子中子树节点数目最多的结点，如果有多个并列最多的则任选一个

轻儿子：父节点中除重儿子以外的儿子

重边： 父节点和重儿子连成的边

轻边：父节点和轻儿子连成的边

重链：由多条重边连接而成的路径

1.整棵树会被剖分成若干条重链

2.轻儿子一定是每条重链的顶点

3.任意一条路径被切分成不超过$logn$条链

数据结构：

fa[u]:存u的父节点

dep[u]存u的深度

son[u]存u的重儿子

sz[u]：存以u为根的子树的结点数

top[u]：存u所在重链的顶点

算法：

1. 第一遍dfs计算出$fa,dep,sz,son$数组
2. 第二遍dfs计算出$top$数组
3. 让两个游标沿着各自的重链向上跳，跳到同一条重链上时，深度较小的游标所指向的点就是$lca$

void dfs1(int u,int father){ // 第一次深搜计算出fa,dep,sz,son数组
    fa[u] = father, dep[u] = dep[father] + 1,sz[u] = 1;
    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if(j == father)continue;
        dfs1(j,u);
        sz[u] += sz[j];
        if(sz[son[u]] < sz[j])son[u] = j;
    }
}

void dfs2(int u,int t){ //u当前结点，t当前结点所在重链的顶部结点，第二次深搜计算top数组
    top[u] = t;
    if(!son[u])return;
    dfs2(son[u],t);
    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if(j == fa[u] || j == son[u])continue;
        dfs2(j,j);
    }
}

int lca(int u,int v){ // 两个游标交替向上跳直到它们跳跃到同一条重链上
    while(top[u] != top[v]){
        if(dep[top[u]] < dep[top[v]])swap(u,v);
        u = fa[top[u]];
    }
    return dep[u] < dep[v]?u:v; // 深度更小也就是更靠近根节点的那一个游标标记的就是lca
}