最近公共祖先(LCA)模板

2022-06-04 14:13:14

以下转自：https://www.cnblogs.com/JVxie/p/4854719.html

首先是最近公共祖先的概念(什么是最近公共祖先？)：

在一棵没有环的树上，每个节点肯定有其父亲节点和祖先节点，而最近公共祖先，就是两个节点在这棵树上深度最大的公共的祖先节点。

换句话说，就是两个点在这棵树上距离最近的公共祖先节点。

所以LCA主要是用来处理当两个点仅有唯一一条确定的最短路径时的路径。

有人可能会问：那他本身或者其父亲节点是否可以作为祖先节点呢？

答案是肯定的，很简单，按照人的亲戚观念来说，你的父亲也是你的祖先，而LCA还可以将自己视为祖先节点。

举个例子吧，如下图所示４和５的最近公共祖先是２，５和３的最近公共祖先是１，２和１的最近公共祖先是１。　

这就是最近公共祖先的基本概念了，那么我们该如何去求这个最近公共祖先呢？

通常初学者都会想到最简单粗暴的一个办法：对于每个询问，遍历所有的点，时间复杂度为O(n*q)，很明显，n和q一般不会很小。

常用的求LCA的算法有：Tarjan（离线）、倍增法（在线）

下面贴两种写法的代码，以HDU 2586 How far away ？为例：

题目大意：

给你一棵树n个节点，m次询问，每次询问树上节点u和v的最小距离。

Tarjan(时间复杂度O(n+Qlogn))

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 using namespace std;

 const int N=4e4+;

 struct node{

     int to,w;

     node(int to,int w):to(to),w(w){}

 };

 struct qnode{

     int to,id;

     qnode(int to,int id):to(to),id(id){}

 };

 vector<node>v[N];

 vector<qnode>q[N];

 bool vis[N];                //vis[i]表示点i是否被访问过

 int res[N],root[N],dis[N];  //res记录答案

 int find(int x){

     return root[x]==x?x:root[x]=find(root[x]);

 }

 void lca(int u){

     vis[u]=true;

     for(int i=;i<v[u].size();i++){

         node t=v[u][i];

         if(!vis[t.to]){

             dis[t.to]=dis[u]+t.w;

             lca(t.to);

             root[t.to]=u;

         }

     }

     for(int i=;i<q[u].size();i++){

         qnode t=q[u][i];

         if(vis[t.to]){

             res[t.id]=dis[u]+dis[t.to]-*dis[find(t.to)];

         }

     }

 }

 int main(){

     int t;

     scanf("%d",&t);

     while(t--){

         int n,m;

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

         memset(vis,false,sizeof(vis));

         memset(dis,,sizeof(dis));

         for(int i=;i<=n;i++){

             root[i]=i;

             v[i].clear();

         }

         for(int i=;i<=m;i++){

             q[i].clear();

         }

         for(int i=;i<=n-;i++){

             int a,b,c;

             scanf("%d%d%d",&a,&b,&c);

             v[a].push_back(node(b,c));

             v[b].push_back(node(a,c));

         }

         for(int i=;i<=m;i++){

             int a,b;

             scanf("%d%d",&a,&b);

             q[a].push_back(qnode(b,i));

             q[b].push_back(qnode(a,i));

         }

         lca(1);
         for(int i=;i<=m;i++){

             printf("%d\n",res[i]);

         }

     }

     return ;

 }

倍增法（时间复杂度O（nlogn+Qlogn））

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<vector>

 #include<algorithm>

 using namespace std;

 const int N=1e5+;

 struct node{

     int to,w;

     node(int to,int w):to(to),w(w){}

 };

 vector<node>v[N];

 int n,m;

 int depth[N],fa[N][],dis[N];

 bool vis[N];

 void init(){

     memset(depth,,sizeof(depth));

     memset(fa,,sizeof(fa));

     memset(dis,,sizeof(dis));

     memset(vis,false,sizeof(vis));

     for(int i=;i<=n;i++) v[i].clear();

 }

 void dfs(int u){

     vis[u]=true;

     for(int i=;i<v[u].size();i++){

         node t=v[u][i];

         if(!vis[t.to]){

             depth[t.to]=depth[u]+;

             fa[t.to][]=u;

             dis[t.to]=dis[u]+t.w;

             dfs(t.to);

         }

     }

 }

 //倍增,处理fa数组

 void bz(){

     for(int j=;j<=;j++){

         for(int i=;i<=n;i++){

             fa[i][j]=fa[fa[i][j-]][j-];

         }

     }

 }

 int lca(int x,int y){

     //保证深度大的点为x

     if(depth[x]<depth[y])

         swap(x,y);

     int dc=depth[x]-depth[y];

     for(int i=;i<;i++){

         if(<<i&dc)                 //一个判断，模拟下就会清楚

             x=fa[x][i];

     }

     if(x==y)    return x;           //如果深度一样，两个点相同，直接返回

     for(int i=;i>=;i--){

         if(fa[x][i]!=fa[y][i]){     //跳2^i不一样，就跳，否则不跳

             x=fa[x][i];

             y=fa[y][i];

         }

     }

     x=fa[x][];

     return x;

 }

 int main(){

     int t;

     scanf("%d",&t);

     while(t--){

         init();

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

         for(int i=;i<=n-;i++){

             int a,b,c;

             scanf("%d%d%d",&a,&b,&c);

             v[a].push_back(node(b,c));

             v[b].push_back(node(a,c));

         }

         dfs();

         bz();

         for(int i=;i<=m;i++){

             int x,y;

             scanf("%d%d",&x,&y);

             printf("%d\n",dis[x]+dis[y]-*dis[lca(x,y)]);

         }

     }

     return ;

 }