python/TangDou/AcWing/LCA/P3379.md

P3379 【模板】最近公共祖先（LCA）

LCA常见的四种求法

一、暴力

操作步骤： ① 求出每个结点的深度 ② 询问两个结点是否重合，若重合，则LCA已经求出 ③ 否则，选择两个点中深度较大的一个，并移动到它的父亲

int depth[N];
int fa[N];

void bfs(int root) {
    queue<int> q;
    q.push(root);
    depth[root] = 1;
    fa[root] = -1;

    while (q.size()) {
        int u = q.front();
        q.pop();
        for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i];
            if (!depth[v]) {
                depth[v] = depth[u] + 1;
                fa[v] = u;
                q.push(v);
            }
        }
    }
}

int lca(int a, int b) {
    if (depth[a] > depth[b]) swap(a, b);
    while (depth[a] < depth[b]) b = fa[b];
    while (a != b) a = fa[a], b = fa[b];
    return a;
}

二、倍增求LCA

#include <bits/stdc++.h>
using namespace std;
const int N = 500010, M = N << 1;

int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

int depth[N];
int f[N][20];

void bfs(int root) {
    queue<int> q;
    q.push(root);
    depth[root] = 1;
    while (q.size()) {
        int u = q.front();
        q.pop();
        for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i];
            if (!depth[v]) {
                depth[v] = depth[u] + 1;
                f[v][0] = u;
                q.push(v);

                for (int k = 1; k <= 19; k++) f[v][k] = f[f[v][k - 1]][k - 1];
            }
        }
    }
}

int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);

    for (int k = 19; k >= 0; k--)
        if (depth[f[a][k]] >= depth[b]) a = f[a][k];

    if (a == b) return a;

    for (int k = 19; k >= 0; k--)
        if (f[a][k] != f[b][k])
            a = f[a][k], b = f[b][k];

    return f[a][0];
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("P3379.in", "r", stdin);
#endif
    memset(h, -1, sizeof h);

    // Q:为什么上面的数组开20，每次k循环到19？
    // 答： cout << log2(500000) << endl;

    int n, m, s;
    scanf("%d %d %d", &n, &m, &s);

    int a, b;
    for (int i = 1; i < n; i++) {
        scanf("%d %d", &a, &b);
        add(a, b), add(b, a);
    }

    bfs(s);

    while (m--) {
        scanf("%d %d", &a, &b);
        cout << lca(a, b) << endl;
    }
    return 0;
}

三、Tarjan算法求LCA

什么是Tarjan(离线)算法呢？顾名思义，就是在一次遍历中把所有询问一次性解决，所以其时间复杂度是O(n+q)。

Tarjan算法的优点在于 相对稳定，时间 复杂度也比较居中，也很 容易理解。

下面详细介绍一下Tarjan算法的基本思路：

1. 任选一个点为根节点，从根节点开始
2. 记u已被访问过
3. 遍历该点u所有子节点j
4. 若是j还有子节点，返回3，否则下一步
5. 合并j到u家族
6. 寻找与当前点u有询问关系的点v,id,
7. 若是v已经被访问过了，lca[id]=find(v)

遍历的话需要用到dfs来遍历(我相信来看的人都懂吧...)，至于合并，最优化的方式就是利用 并查集 来合并两个节点。

下面上伪代码：

//merge和find为并查集合并函数和查找函数
tarjan(u){
    st[u] = true;
    for each(u,v){   //访问所有u子节点v
        tarjan(v);   //继续往下遍历
        p[v] = find(u);//合并v到u上
    }
    for each(u,v){   //访问所有和u有询问关系的v
        如果v被访问过;
        u,v的最近公共祖先为find(v);
    }
}

个人感觉这样还是有很多人不太理解，所以我打算模拟一遍给大家看。

建议拿着纸和笔跟着我的描述一起模拟！！

假设我们有一组数据 9个节点 8条边 联通情况如下：

1-2，1-3，2-4，2-5，3-6，5-7，5-8，7-9 即下图所示的树

设我们要查找最近公共祖先的点为9-8，4-6，7-5，5-3

设f[]数组为并查集的父亲节点数组，初始化f[i]=i，vis[]数组为是否访问过的数组，初始为0;

下面开始模拟过程：

取1为 根节点，往下搜索 发现有两个儿子2和3；

先搜2，发现2有两个儿子4和5，先搜索4，发现4没有子节点，则寻找与其有关系的点；

发现6与4有关系，但是vis[6]=0，即6还没被搜过，所以 不操作；

发现没有和4有询问关系的点了，返回此前一次搜索，更新vis[4]=1；

表示4已经被搜完，更新f[4]=2，继续搜5，发现5有两个儿子7和8;

先搜7，发现7有一个子节点9，搜索9，发现没有子节点，寻找与其有关系的点；

发现8和9有关系，但是vis[8]=0,即8没被搜到过，所以不操作；

发现没有和9有询问关系的点了，返回此前一次搜索，更新vis[9]=1；

表示9已经被搜完，更新f[9]=7，发现7没有没被搜过的子节点了，寻找与其有关系的点；

发现5和7有关系，但是vis[5]=0，所以 不操作；

发现没有和7有关系的点了，返回此前一次搜索，更新vis[7]=1；

表示7已经被搜完，更新f[7]=5，继续搜8，发现8没有子节点，则寻找与其有关系的点；

发现9与8有关系，此时vis[9]=1，则他们的最近公共祖先为find(9)=5； (find(9)的顺序为f[9]=7-->f[7]=5-->f[5]=5 return 5;)

发现没有与8有关系的点了，返回此前一次搜索，更新vis[8]=1； 表示8已经被搜完，更新f[8]=5，发现5没有没搜过的子节点了，寻找与其有关系的点；

发现7和5有关系，此时vis[7]=1，所以他们的最近公共祖先为find(7)=5； (find(7)的顺序为f[7]=5-->f[5]=5 return 5;)

又发现5和3有关系，但是vis[3]=0，所以不操作，此时5的子节点全部搜完了；

返回此前一次搜索，更新vis[5]=1，表示5已经被搜完，更新f[5]=2；

发现2没有未被搜完的子节点，寻找与其有关系的点；

又发现没有和2有关系的点，则此前一次搜索，更新vis[2]=1；

表示2已经被搜完，更新f[2]=1，继续搜3，发现3有一个子节点6；

搜索6，发现6没有子节点，则寻找与6有关系的点，发现4和6有关系；

此时vis[4]=1，所以它们的最近公共祖先为find(4)=1;

(find(4)的顺序为f[4]=2-->f[2]=2-->f[1]=1 return 1;)

发现没有与6有关系的点了，返回此前一次搜索，更新vis[6]=1，表示6已经被搜完了；

更新f[6]=3，发现3没有没被搜过的子节点了，则寻找与3有关系的点；

发现5和3有关系，此时vis[5]=1，则它们的最近公共祖先为find(5)=1；

(find(5)的顺序为f[5]=2-->f[2]=1-->f[1]=1 return 1;)

发现没有和3有关系的点了，返回此前一次搜索，更新vis[3]=1；

更新f[3]=1，发现1没有被搜过的子节点也没有有关系的点，此时可以退出整个dfs了。

经过这次dfs我们得出了所有的答案，有没有觉得很神奇呢？是否对Tarjan算法有更深层次的理解了呢？

Code

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
const int N = 500010, M = N << 1;

//链式前向星
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

vector<PII> query[N]; // query[u]: first:询问的另一个顶点; second:询问的编号

int n, m, s;
int p[N];   // 并查集数组
bool st[N]; // tarjan算法求lca用到的是否完成访问的标识
int lca[N]; // 结果数组

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]); //路径压缩
    return p[x];
}

void tarjan(int u) {
    // ① 标识u已访问
    st[u] = true;
    //② 枚举u的临边，tarjan没有访问过的点
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (!st[j]) {
            tarjan(j);
            //③ 完成访问后，j点加入u家族
            p[j] = u;
        }
    }
    //④ 每个已完成访问的点，记录结果
    for (auto q : query[u]) {
        int v = q.first, id = q.second;
        if (st[v]) lca[id] = find(v);
    }
}

int main() {
    memset(h, -1, sizeof h);
    scanf("%d %d %d", &n, &m, &s);

    int a, b;
    for (int i = 1; i < n; i++) {
        scanf("%d %d", &a, &b);
        add(a, b), add(b, a);
    }

    for (int i = 1; i <= m; i++) {
        scanf("%d %d", &a, &b);
        query[a].push_back({b, i});
        query[b].push_back({a, i});
    }

    //初始化并查集
    for (int i = 1; i <= n; i++) p[i] = i;
    tarjan(s);

    //输出答案
    for (int i = 1; i <= m; i++) printf("%d\n", lca[i]);
    return 0;
}

四、RMQ+ST

挖坑待填 https://blog.csdn.net/m0_60630928/article/details/123160718?share_token=94367124-164f-4ecb-bddb-be496df1a2cd　　　　

//3.95s /  227.49MB /  1.67KB C++14 (GCC 9) O2
 
#include<bits/stdc++.h>
using namespace std;
const int N=500005;
vector<int>vec[N];
//记录每个结点可以走向哪些结点 
int f[N*2][21],mem[N*2][21],depth[N*2],first[N],vis[N*2],lg[N];
//f:记录深度序列区间中的最小深度
//mem:记录 找到深度序列区间中的最小深度 时的对应结点（在欧拉序列中） 
//depth:在dfs过程中记录遍历到每个点时的对应深度
//first:记录每个结点第一次出现时在欧拉序列中的位置
//vis:欧拉序列
//lg；lg[i]==log_{2}{i}+1 
int cnt=0,n,m,s;
//cnt:每走到一个点计一次数
 
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
} 
 
void dfs(int now,int dep)
{
	if(!first[now]) first[now]=++cnt;//第一次遍历到该点 
	depth[cnt]=dep,vis[cnt]=now;
	for(int i=0;i<vec[now].size();i++)
	{
		if(first[vec[now][i]]) continue;//是该结点的父节点，跳过 
		else dfs(vec[now][i],dep+1);
		++cnt;
		depth[cnt]=dep,vis[cnt]=now;//深搜完了vec[now][i]下的分支，回到当前结点 now
	}
}
 
void RMQ()
{
	for(int i=1;i<=cnt;i++)
	{
		lg[i]=lg[i-1]+((1<<lg[i-1])==i);
		f[i][0]=depth[i];//区间长度为1时，该区间内深度的最小值就是该结点的深度 
		mem[i][0]=vis[i];
	}
	for(int j=1;(1<<j)<=cnt;j++)//枚举的区间长度倍增 
		for(int i=1;i+(1<<j)-1<=cnt;i++)//枚举合法的每个区间起点 
		{
			if(f[i][j-1]<f[i+(1<<(j-1))][j-1])//深度最小的点在前半个区间 
			{
				f[i][j]=f[i][j-1];
				mem[i][j]=mem[i][j-1];
			}
			else//深度最小的后半个区间 
			{
				f[i][j]=f[i+(1<<(j-1))][j-1];
				mem[i][j]=mem[i+(1<<(j-1))][j-1];
			}
		}
}
 
int ST(int x,int y)
{
	int l=first[x],r=first[y];//找到输入的两个结点编号对应在欧拉序列中第一次出现的位置 
	if(l>r) swap(l,r);
	int k=lg[r-l+1]-1;
	if(f[l][k]<f[r-(1<<k)+1][k]) return mem[l][k];
	else return mem[r-(1<<k)+1][k];
}
 
int main()
{
	n=read(),m=read(),s=read();
	for(int i=1;i<n;i++)
	{
		int a,b;
		a=read(),b=read();
		vec[a].push_back(b);
		vec[b].push_back(a);
	}
	dfs(s,0);//打表，给first、depth、vis赋值，给RMQ奠定基础 
	/*cout<<"各结点第一次出现的位置："<<endl; 
	for(int i=1;i<=n;i++)
		cout<<first[i]<<' ';
	cout<<endl;
	cout<<"欧拉序列："<<endl; 
	for(int i=1;i<=2*n;i++)
		cout<<vis[i]<<' ';
	cout<<endl;
	cout<<"深度序列"<<endl; 
	for(int i=1;i<=2*n;i++)
		cout<<depth[i]<<' ';
	cout<<endl;*/
	RMQ();//打表，给f和mem赋值 ,给ST奠定基础 
	while(m--)
	{
		int x,y;
		x=read(),y=read();
		printf("%d\n",ST(x,y));
	}
	return 0;
}