算法学习笔记（LCA）

$LCA$：树上两个点的最近公共祖先。（两个节点所有公共祖先中，深度最大的公共祖先）

$LCA$的性质：

1. 在所有公共祖先中，$LCA(x,y)$到$x$和$y$的距离都最短。
2. $x$，$y$之间最短的路径经过$LCA(x,y)$。
3. $x$，$y$本身也可以是它们自己的公共祖先。若$y$是$x$的祖先，则有$LCA(x,y)=y$。
4. $LCA(x,y,z)=LCA(x,LCA(y,z))$
5. $LCA(x_1,x_2,...,x_n)=LCA(dfs序最大点，dfs序最小点)$

本文主要介绍求$LCA$的两种方法：倍增法和$Tarjan$。

先引入例题：

【模板】LCA

题目描述

给定一个$n$个点以结点$1$为根的树，有$q$次询问，每次询问给出两个点$u,v$，求$LCA(u,v)$。

$LCA(u,v)$表示$u,v$的最近公共祖先。

输入描述

第一行一个整数$n$表示结点个数。$(1\le n\le 2\times 10^5)$

第二行$n-1$个整数，表示$2\sim n$结点的父亲。

第三行一个整数$q$，表示询问次数。$(1\le q\le 2\times 10^5)$

接下来$q$行，每行两个整数$u,v$。$(1\le u,v\le n)$

输出描述

对于每次询问，一行一个整数表示结果。

输入样例1

5
1 1 2 3
3
1 2
2 4
1 5

输出样例1

1
2
1

倍增法：

大体就是让两个点不断向上走，直到走到最近的相同的点。如何快速地走？这里就需要用倍增法来实现。倍增法的原理利用了二进制的性质：任意一个数字都可以由一个或几个$2$的幂相加得到，所以可以以$1,2,4,\mathrm{8...}$这种$2$的幂作为一步的长度向上走。

因为我们不知道应该走多大，所以应该先尝试走大数，能走即走，再尝试走小步。

为了快速地进行跳跃，我们需要预处理出一个帮助我们进行跳跃的数组$fa[N][20]$（$fa[x][i]$表示从$x$出发向上走$2^i$步到达的位置）。计算$fa$数组时用到了$dp$的思路，这里有个递推公式：$fa[x][i]=fa[fa[x][i-1]][i-1]$，意思是从点$x$出发，先跳$2^{i-1}$步，再跳$2^{i-1}$步。由小推到大。

得到这个数组之后，就可以快速地计算$LCA$了。具体步骤如下：

先将点$x$和点$y$处理至同一深度。让深度较大的数以祖先链上深度与深度较小的那个点相等的点为目标进行跳跃。特殊的，如果该点就是深度较浅的那个点，则使用上述$LCA$的性质中的第三条。

之后，点$x$和点$y$再同时向上跳跃。直至分别跳到$LCA(x,y)$的两个儿子上。即$x\ne y$并且$fa[x][0]=fa[y][0]$。

最后得到的$fa[x][0]$就是$LCA(x,y)$。

时间复杂度为：$O(nlo{g}_{2}n+qlo{g}_{2}n)$

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 9, T = 20;

vector<int> g[N];
int fa[N][30], dep[N];

void dfs(int x)
{
    dep[x] = dep[fa[x][0]] + 1;     //预处理各个节点深度

    //预处理fa数组
    for(int i = 1; i <= T; ++i) fa[x][i] = fa[fa[x][i - 1]][i - 1];

    for(const auto &i : g[x])
    {
        dfs(i);
    }
}

int lca(int u, int v)
{
    if(dep[u] < dep[v]) swap(u, v);     //不妨设点u深度大于等于点v
    
    //跳跃，先走大步再走小步
    //将u点跳至于点v相同高度
    for(int i =  T; i >= 0; --i)
    {
        if(dep[fa[u][i]] >= dep[v]) u = fa[u][i];
    }
    if(u == v) return u;

    //一起往上跳
    for(int i = T; i >= 0; --i)
    {
        if(fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
    }

    return fa[u][0];
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    int n; cin >> n;
    for(int i = 2; i <= n; ++i)
    {
        cin >> fa[i][0];
        g[fa[i][0]].push_back(i);
    }
    dfs(1);
    int q; cin >> q;
    while(q--)
    {
        int u, v; cin >> u >> v;
        cout << lca(u, v) << '\n';
    }
    
	return 0;
}

Tarjan

大概流程：

还是采用$dfs$，访问到一个点的时候，先标记被访问，然后向下处理它的儿子节点，看儿子节点是否为所求$LCA$有关的点，处理完儿子节点之后回溯上来时再处理自己，看自己是否为所求$LCA$有关的点。再向上合并，合并采用并查集进行合并且使用路径压缩。

因为有多组询问，所以需要将询问离线。

对于一对点中的一个点处理的时候，若另一个点已经被访问过了，那么那个点在的并查集中的根节点就是它们的$LCA$，这和$dfs$的性质有关。都访问到的时候，它们一定在同一棵子树上，并且这颗子树的根显然就是它们的$LCA$。

时间复杂度为：$O(n+q)$

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 9;

int pre[N], dep[N], ans[N], fa[N];
vector<int> g[N];
vector<pair<int, int>> Q[N];
bitset<N> vis;

//并查集基础操作
int find(int x)
{
    return pre[x] = (pre[x] == x ? x : find(pre[x]));
}

void merge(int x, int y)    //将深度大的向深度小的合并，向上合并
{
    int fx = find(x), fy = find(y);
    if(dep[fx] < dep[fy]) swap(fx, fy);
    pre[fx] = fy;
}

void dfs(int x)
{
    //顺手计算深度，合并时使用
    dep[x] = dep[fa[x]] + 1;
    vis[x] = true;

    for(const auto &y : g[x]) dfs(y);   //先处理所有儿子

    for(const auto &[y, id] : Q[x])     //在处理自己
    {
        if(!vis[y]) continue;       //如果对方未被访问就跳过
        ans[id] = find(y);
    }

    merge(x, fa[x]);
}

void solve()
{
    int n; cin >> n;
    for(int i = 1; i <= n; ++i) pre[i] = i;
    for(int i = 2; i <= n; ++i)
    {
        cin >> fa[i];
        g[fa[i]].push_back(i);
    }

    int q; cin >> q;
    //将询问离线
    for(int i = 1; i <= q; ++i)
    {
        int x, y; cin >> x >> y;
        Q[x].push_back({y, i});
        Q[y].push_back({x, i});
    }

    dfs(1);

    for(int i = 1; i <= q; ++i) cout << ans[i] << '\n';
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
    while(_--) solve();
    return 0;
}

$LCA$可以求树上两点之间的最短距离，也可以做树上差分，这里就不过多赘述。