LCA两种在线解法(RMQ+欧拉序、树上倍增)模板

LCA（最近公共祖先）解法模板，附有详细代码注释

我们知道，最近公共祖先是指有根树上找出任意两个节点，u，v的最近的公共祖先。
这是洛谷的模板题：
最近公共祖先LCA
解释都在代码里：

树上倍增

#pragma GCC optimize(2)
#include
using namespace std;
#define IOS ios::sync_with_stdio(0)
#define ull unsigned ll
#define uint unsigned
#define pai pair
#define pal pair
#define IT iterator
#define pb push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);++i)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);--i)
#define endl '\n'
#define ll long long
const int N=500010;
int head[N],tot;
struct node
{int to,nxt;
}tree[N<<1];//定义节点
void add(int x,int y)
{tree[++tot].to=y;tree[tot].nxt=head[x];head[x]=tot;
}//链式前向星存图
int depth[N];//depth数组用来存每一个节点的深度；
int fa[N][20];//fa[i][j]表示节点i的2^j级祖先；
int lg[N];//倍增遍历的lg数组;void dfs(int now,int fath)//now表示当前节点，fath表示它的直接父亲节点
{fa[now][0]=fath;//当前节点的父亲；depth[now]=depth[fath]+1;//当前节点的深度就是父亲节点的深度+1;for(int i=1;i<lg[depth[now]];++i){fa[now][i]=fa[fa[now][i-1]][i-1];//实际上是一个小递归，就是一个节点的2^i级祖先为它的2^i级祖先的2^i级祖先;}for(int i=head[now];i;i=tree[i].nxt){if(tree[i].to!=fath)dfs(tree[i].to,now);}
}//以上dfs实际上是一种预处理，找出每一个节点的2^i级祖先。
int LCA(int x,int y)
{if(depth[x]<depth[y])//为了方便处理，我们设x的深度大于y的深度;swap(x,y);while(depth[x]>depth[y]){x=fa[x][lg[depth[x]-depth[y]]-1];//先让x跳到与y的同一深度;}if(x==y)//如果x是y的祖先，那么它们的公共祖先为x;return x;for(int k=lg[depth[x]]-1;k>=0;--k)//两个节点一起往上跳，每次的幅度就是lg数组if(fa[x][k]!=fa[y][k])//因为一直不相等，所以我们会跳到LCA的下一层x=fa[x][k],y=fa[y][k];return fa[x][0];//最后返回下一层的父亲，也就是我们要求的LCA;
}
int main()
{int n,m,s;scanf("%d%d%d",&n,&m,&s);for(int i=1;i<=n-1;++i){int x,y;scanf("%d%d",&x,&y);add(x,y);add(y,x);}for(int i=1;i<=n;++i){lg[i]=lg[i-1]+(1<<lg[i-1]==i);}//常数优化;dfs(s,0);for(int i=1;i<=m;++i){int x,y;scanf("%d%d",&x,&y);printf("%d\n",LCA(x,y));}return 0;
}

RMQ+欧拉序：

#pragma GCC optimize(2)
#include
using namespace std;
#define IOS ios::sync_with_stdio(0)
#define ull unsigned ll
#define uint unsigned
#define pai pair
#define pal pair
#define IT iterator
#define pb push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);++i)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);--i)
#define endl '\n'
#define ll long long
const int maxn = 500005;
const int maxm = 1000005;
int head[maxn],nxt[maxm],to[maxm],cnt;
int id[maxm],vis[maxm],depth[maxm],tot;
int f[maxm][20],lg[maxm];
//定义dp[i][j] 表示下标i开始长度为2^j的区间的极值。如：dp[2][1]表示区间[2,3]的极值
inline int read()
{int sum = 0,p = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-')p = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){(sum *= 10)+= ch - '0';ch = getchar();}return sum * p;
}//快读void add(int x,int y)//链式前向星加边
{nxt[++cnt] = head[x];to[cnt] = y;head[x] = cnt;return;
}void dfs(int u,int fa,int dep)//u代表当前节点，fa是当前节点的父亲，dep是当前节点的深度
{id[u] = ++tot;//id[u]表示在欧拉序中第一次被访问时的下标。vis[tot] = u;//vis[i]存的是第i个节点在欧拉序中的编号depth[tot] = dep;//depth[]是存节点的深度for(int i = head[u];i;i = nxt[i])//链式前向星遍历{int v = to[i];if(v == fa)continue;dfs(v,u,dep+1);vis[++tot] = u;depth[tot] = dep;}return;
}//欧拉序处理每个节点得到id[u]，vis[i],depth[i];void RMQ()
{for(int i = 1;i <= tot;i++)//tot是跑过欧拉序后的总点数lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);//常数优化预处理for(int i = 1;i <= tot;i++)f[i][0] = i;for(int j = 1;(1 << j) <= tot;j++)for(int i = 1;i + (1 << j) - 1 <= tot;i++){int a = f[i][j-1];int b = f[i + (1 << (j - 1))][j - 1];if(depth[a] <= depth[b])f[i][j] = a;elsef[i][j] = b;}return;
}int LCA(int x,int y)
{int r = id[x];int l = id[y];if(r < l)swap(r,l);int k = lg[r - l + 1] - 1;int a = f[l][k];int b = f[r - (1 << k) + 1][k];if(depth[a] <= depth[b])return vis[a];elsereturn vis[b];
}int main()
{int n = read(),m = read(),s = read();int x,y;for(int i = 1;i < n;i++){x = read(),y = read();add(x,y);add(y,x);}dfs(s,0,1);RMQ();for(int i = 1;i <= m;i++){x = read(),y = read();printf("%d\n",LCA(x,y));}return 0;
}

推荐使用树上倍增解法，可以存储的信息量大且代码量少。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！