14 solutions

  • 13
    @ 2021-10-6 20:41:44

    本题的核心思路：倍增。 如果暴力求LCA，要从两个节点开始，一步一步往根节点方向走，记录路径，再从路径最后（就是根节点）开始比较，比较什么时候后出现不同。代码如下：

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

const int MAXN=500000+5;
const int MAXM=500000+5;

int head[MAXN];
int father[MAXN];
bool visited[MAXM];
int bianshu;

struct edge
{
	int v,next;
}g[2*MAXM];

void addedge(int u,int v)
{
	g[++bianshu].next=head[u];
	g[bianshu].v=v;
	head[u]=bianshu;
	return;
}

queue <int> q;
int s;
void bfs()
{
	q.push(s);
	while(!q.empty())
	{
		int ppp=q.front();
		q.pop();
		for(int i=head[ppp];i;i=g[i].next)
		{
			if(!visited[g[i].v])
			{
				visited[g[i].v]=true;
				father[g[i].v]=ppp;
				q.push(g[i].v);
			}
		}
	}
	
}

int path1[MAXN];
int path2[MAXN];
int cntp1,cntp2;
int ans;
int main()
{
	int n,q;
	int uu,vv;
	int a,b;
	int LCA,a1,a2;
	scanf("%d%d%d",&n,&q,&s);
	for(int i=1;i<=n-1;++i)
	{
		scanf("%d%d",&uu,&vv);
		addedge(uu,vv);
		addedge(vv,uu);
	}
	father[s]=s;
	visited[s]=true;
	bfs();
	for(int i=1;i<=q;++i)
	{
		scanf("%d%d",&a,&b);
		for(int j=a;j!=s;j=father[j])
		{
			path1[++cntp1]=j;
		}
		path1[++cntp1]=s;
		for(int j=b;j!=s;j=father[j])
		{
			path2[++cntp2]=j;
		}
		path2[++cntp2]=s;
		while(path1[cntp1--]==path2[cntp2--])
		{
			ans=path1[cntp1+1];
		}
		printf("%d\n",ans);
		memset(path1,0,sizeof(path1));
		memset(path2,0,sizeof(path2));
		cntp1=0;
		cntp2=0;
		ans=0;
	}
	return 0;
}

    然而，暴力的时间和空间复杂度根本无法接受。 我们来思考下面这个问题：我为什么要一个一个跳到根节点呢？ 于是乎，“倍增”就出现了。 定义jump[a][b]数组的意义如下： 编号为a的点往根节点方向走(2^b)次之后的点的编号。 每一次不需要一个一个往根节点方向走，而是采取了一种类似于跳跃的模式。 往根节点方向走（2^0)次，即得到这个点的父亲节点。所以先初始化数组：

    for(int i=1;i<=n;++i)
	{
		jump[i][0]=father[i];
	}//jump初值

    然后，再将jump[i][1] jump[i][2]等求出来。 jump[i][j]可以通过jump[i][j-1]再往根节点方向走j-1次得到。 推得状态转移方程：jump[i][j]=jump[jump[i][j-1]][j-1];

    for(int j=1;j<=30;++j)
	{
		for(int i=1;i<=n;++i)
		{
			jump[i][j]=jump[jump[i][j-1]][j-1];
		}
	}//初始化jump数组

    接下来我们要开始求最近公共祖先了。然而，如果节点a深度为16，节点b深度为32，所求得的跳跃次数、路径长度都是不一样的，我们又要记录路径然后从后往前比较。 于是乎，我们想了一个办法：先把a，b跳跃到同一深度，再进行剩下的跳跃。（有更简便写法）

    if(dep[a]>dep[b]) //每次判断是否跳跃(1<<k)次，跳跃到同一深度 
		{
			for(int k=30;k>=0;--k)
			{
				if(tmp>=(1<<k))
				{
					a=jump[a][k];
				}
			} 
		}
		else if(dep[b]>dep[a]) 
		{
			for(int k=30;k>=0;--k)
			{
				if(tmp>=(1<<k))
				{
					b=jump[b][k];
				}
			} 
		}//使得a,b位于同一深度

    如果这个时候已经跳到同一个点，即a==b，则直接输出，否则进行我们最后的跳跃。只要jump[i][k]!=jump[j][k]（k取值可以不做限制，因为无意义的那些范围的jump值均会是0）我们就跳跃。跳跃完之后，你会惊奇的发现father[a]==father[b];（可以自己模拟一下）所以我们输出任意一边的father均可。 一些没提到的细节和代码如下：

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

const int MAXN=500000+5;
const int MAXM=1000000+5;

int head[MAXN];//链式前向星 

int father[MAXN];//父亲节点 

bool visited[MAXN];

int bianshu;

struct edge//链式前向星 
{
	int v,next;
}g[2*MAXM];//双向边，记得开2倍范围 

void addedge(int u,int v)//链式前向星无权值加边 
{
	g[++bianshu].next=head[u];
	g[bianshu].v=v;
	head[u]=bianshu;
	return;
} 

queue <int> q;//bfs用
 
int dep[MAXN];//每个点的深度 

void bfs(int s,int depth)//求father 
{
	q.push(s);
	dep[s]=depth;
	while(!q.empty())
	{
		int ppp=q.front();
		q.pop();
		for(int i=head[ppp];i;i=g[i].next)//遍历 
		{
			if(!visited[g[i].v])
			{
				visited[g[i].v]=true;
				father[g[i].v]=ppp;
				dep[g[i].v]=dep[ppp]+1;//存储深度，比父亲节点深度大1 
				q.push(g[i].v);
			}
		}
	}
}

int jump[MAXN][35];//定义：j[a][b]为a号点往根节点方向走(1<<b)次后的节点编号 

int main()
{
	int n,q,s;
	int uu,vv;
	int a,b;
	int tmp;//深度差 
	
	scanf("%d%d",&n,&q);//有时候需要读入s 
	s=1; 
	
	for(int i=1;i<=n-1;++i)
	{
		scanf("%d%d",&uu,&vv);
		addedge(uu,vv);
		addedge(vv,uu);
	}//加边 
	
	father[s]=0;//注意：father[根]一定要设为0，否则后面跳跃时出问题 
	visited[s]=true;
	bfs(s,1);//求father数组 
	
	for(int i=1;i<=n;++i)
	{
		jump[i][0]=father[i];
	}//jump初值 
	for(int j=1;j<=30;++j)
	{
		for(int i=1;i<=n;++i)
		{
			jump[i][j]=jump[jump[i][j-1]][j-1];
		}
	}//初始化jump数组 
	 
	while(q--)//操作 
	{
		scanf("%d%d",&a,&b);
		
		tmp=(dep[a]>dep[b]?dep[a]-dep[b]:dep[b]-dep[a]);//深度差值 
		
		if(dep[a]>dep[b]) //每次判断是否跳跃(1<<k)次，跳跃到同一深度 
		{
			for(int k=30;k>=0;--k)
			{
				if(tmp>=(1<<k))
				{
					a=jump[a][k];
					tmp-=(1<<k);
				}
			} 
		}
		else if(dep[b]>dep[a]) 
		{
			for(int k=30;k>=0;--k)
			{
				if(tmp>=(1<<k))
				{
					b=jump[b][k];
					tmp-=(1<<k);
				}
			} 
		}//使得a,b位于同一深度 
		
		if(a==b)//跳到同一个点，即LCA就是当前的点，需要特判。 
		{
			printf("%d\n",a);
			continue;
		}
		for(int k=30;k>=0;--k)
		{
			if((jump[a][k]^jump[b][k]))//异或符号^在此处等价于！= 符号 
			{
				a=jump[a][k];
				b=jump[b][k];
			}
		}//跳2的k次方次
		 
		printf("%d\n",father[a]);
	}
	return 0;
}

    感谢阅读我这一篇又臭又长的题解。

    • @ 2021-10-15 20:59:27

      好像有一句写错了 求jump[i][1] jump[i][2]的时候 jump[i][j]是要通过jump[i][j-1]再往根节点方向走2（j−1）2^（j-1）次得到

    • @ 2021-10-15 21:00:08

      就是说2的j-1次方 次

    • @ 2023-10-17 20:07:21

      %%%

    • @ 2024-10-23 18:11:13

      @ 试过了代码，TLE了

    • @ 2024-10-23 18:11:34

      试过了代码，TLE了

  • 4
    @ 2022-2-2 17:03:34

    tg重点知识点：LCA

    文件头

    求LCA的基本方式：

    1. 在线法

    代表：倍增，rmq

    这里介绍倍增法。

    先预处理出每一个节点的 2k2^k 级祖先以及深度。

    求LCA时，先让两个节点深度相同，再从大到小枚举 kk ，如果 xx 的 kk 级祖先不等于 yy 的 kk 级祖先就往上跳。

    因为我们跳的是LCA的下一层，所以要输出 xx 的 00 级祖先。

    核心代码：

    vector<int> g[500001];
int n,q;
int depth[500001],f[500001][31];
void dfs(int x, int fa)
{
	depth[x]=depth[fa]+1;
	f[x][0]=fa;
	For(i,1,log2(depth[x])+1)
		f[x][i]=f[f[x][i-1]][i-1];
	For(i,0,g[x].size()-1)
		if(g[x][i]!=fa)
			dfs(g[x][i],x);
}
int lca(int x, int y)
{
	if(depth[y]<depth[x]) swap(y,x);
	while(depth[y]>depth[x]) y=f[y][(int)log2(depth[y]-depth[x])];
	if(x==y) return x;
	ForDown(k,log2(depth[y]),0)
	{
		if(f[x][k]!=f[y][k])
		{
			x=f[x][k],y=f[y][k];
		}
	}
	return f[x][0];
}
signed main()
{
	read(n,q);
	For(i,1,n-1)
	{
		int u,v;
		read(u,v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1,1);
	//cout<<"wedrftgyhujikoswerdtfyguh"<<endl;
	while(q--)
	{
		int x,y;
		read(x,y);
		write_with_endl(lca(x,y));
	}
	return 0;
}

    复杂度 O(qlogn)O(qlogn)

    1. 离线法

    代表：tarjan

    把所有询问存下来，然后在回溯时将并查集中当前节点的“父亲”设为它的父节点。然后如果有一个询问的两个点都算过了，从并查集中找结果存进来。最后输出。

    核心代码：

    int n,m,s;
struct Edge
{
    int v,nxt;
}query[1000001];
int head[500001],cnt=0;
vector<int> g[500001];
int lca[1000001];
void add(int x, int y)
{
    query[++cnt]=(Edge){y,head[x]};
    head[x]=cnt;
}

bool used[500001];
int f[500001];
int find(int x)
{
    return f[x]==x ? f[x] : f[x]=find(f[x]);
}
void tarjan(int x)
{
    used[x]=1;
    For(i,0,g[x].size()-1)
    {
        if(used[g[x][i]]) continue;
        tarjan(g[x][i]);
        f[g[x][i]]=x;
    }
    for(int i=head[x];i;i=query[i].nxt)
    {
        if(used[query[i].v])
        {
            lca[i%2+i]=find(query[i].v);
        }
    }
}

int main()
{
    read(n);read(m);read(s);
    For(i,1,n) f[i]=i;
    For(i,1,n-1)
    {
        int u,v;
        read(u);read(v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    For(i,1,m)
    {
        int u,v;
        read(u);read(v);
        add(u,v);
        add(v,u);
    }
    tarjan(s);
    For(i,1,m)
    {
        write(lca[2*i]);
        putchar('\n');
    }
    return0;
}

    复杂度 O(n)O(n)。

    • 3
      @ 2021-12-5 21:03:51

      倍增法求 LCA 。

      #include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::endl;

int n, q, u, v, fa[500005][20], dep[500005];
std::vector<int> g[500005];

void bfs(int root) {
    memset(dep, 0x3f, sizeof(dep));
    std::queue<int> q;
    dep[0] = 0;
    dep[root] = 1;
    q.push(root);
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        for (int v : g[t]) {
            if (dep[v] > dep[t] + 1) {
                dep[v] = dep[t] + 1;
                q.push(v);
                fa[v][0] = t;
                for (int k = 1; k < 20; k++) {
                    fa[v][k] = fa[fa[v][k - 1]][k - 1];
                }
            }
        }
    }
}

int lca(int a, int b) {
    if (dep[a] < dep[b]) std::swap(a, b);
    for (int k = 19; k >= 0; k--) {
        if (dep[fa[a][k]] >= dep[b]) {
            a = fa[a][k];
        }
    }
    if (a == b) return a;
    for (int k = 19; k >= 0; k--) {
        if (fa[a][k] != fa[b][k]) {
            a = fa[a][k];
            b = fa[b][k];
        }
    }
    return fa[a][0];
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i < n; i++) {
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    bfs(1);
    while (q--) {
        scanf("%d%d", &u, &v);
        printf("%d\n", lca(u, v));
    }
    return 0;
}
      • 2
        @ 2022-5-21 7:46:40

        来点不一样的，用树链剖分求LCA。 先把树剖成链，记录每个点uu所在链的最顶端节点 toputop_u， 每次往上跳即可。

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

/***********************

Author : ACgod
Date : 2022/5/21
School : Xiamen No.1 High School of Fujian

***********************/

#define reg register
#define rep(i, a, b) for(register int i = a; i <= b; i ++)
#define pb push_back

vector<int> e[500005];
int n, q;

template <class T> T read() {
  reg T s=0,f=1; reg char ch = getchar();
  while(ch<'0'||ch>'9')ch=getchar();
  while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
  return f*s;
}

int maxson[500005], size[500005];
int top[500005], dep[500005];
int fat[500005];

void dfs1(int u, int fa) {
  dep[u] = dep[fa] + 1;
  fat[u] = fa;
  int sizeofson = 0;
  for(int i = 0; i < e[u].size(); i ++) {
    int to = e[u][i];
    if(to == fa) continue;
    dfs1(to, u);
    size[u] += size[to];
    if(size[to] > sizeofson) {
      maxson[u] = to;
      sizeofson = size[to];
    }
  }
  size[u]++;
}

void dfs2(int u, int topf, int fa) {
  top[u] = topf;
  for(int i = 0; i < e[u].size(); i ++) {
    int to = e[u][i];
    if(to == fa) continue;
    if(maxson[u] == to) {
      dfs2(to, topf, u);
    }
    else dfs2(to, to, u);
  }
}

int lca(int x, int y) {
  if(dep[top[x]] < dep[top[y]]) swap(x, y);
  return top[x] == top[y] ? (dep[x] < dep[y] ? x : y ): lca(fat[top[x]], y);
}

int main() {
  n = read<int>(), q = read<int>();
  rep(i, 1, n - 1) {
    int u, v;
    u = read<int>(), v = read<int>();
    e[u].pb(v), e[v].pb(u);
  }
  dfs1(1, 0);
  dfs2(1, 1, 0);
  rep(i, 1, q) {
    int x, y;
    x = read<int>(), y = read<int>();
    printf("%d\n", lca(x, y));
  }
  return 0;
}
        • 1
          @ 2025-7-30 14:49:19

          很模板的一道LCA，主要利用了倍增

          看代码吧

          using namespace std;
typedef long long ll;
const int N=500005;
int n,m;
vector<int> G[N];//用的是vector存边
int dep[N],fa[N][20];//fa[i][j]为i的(1<<j)级祖先，dep[i]为i的深度

void Dfs(int u,int f,int d){//预处理fa与深度dep数组
	fa[u][0]=f;dep[u]=d;
	for(int i=1;i<=19;i++)
		fa[u][i]=fa[fa[u][i-1]][i-1];//一步步往上跳
	for(int v:G[u]){
		if(v!=f)Dfs(v,u,d+1);
	}
}

int lca(int x,int y){//求最近公共祖先
	if(dep[x]<dep[y])swap(x,y);
	for(int k=19;k>=0;k--){
		if(dep[fa[x][k]]>=dep[y]){
			x=fa[x][k];
		}
	}
	if(x==y)return x;
	for(int k=19;k>=0;k--){
		if(fa[x][k]!=fa[y][k]){
			x=fa[x][k];
			y=fa[y][k];
		}
	}
	return fa[x][0];
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n-1;i++){
		int x,y;
		cin>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);//存双向边
	}
	Dfs(1,0,1);//起始节点，起始节点的父节点，起始节点的深度
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		cout<<lca(x,y)<<'\n';
	}
	return 0;
}
          • 1
            @ 2025-1-15 10:45:04 
            #include<bits/stdc++.h>
using namespace std;

const int MAXN=500000+5;
const int MAXM=1000000+5;

int head[MAXN];//链式前向星 

int father[MAXN];//父亲节点 

bool visited[MAXN];

int bianshu;

struct edge//链式前向星 
{
	int v,next;
}g[2*MAXM];//双向边，记得开2倍范围 

void addedge(int u,int v)//链式前向星无权值加边 
{
	g[++bianshu].next=head[u];
	g[bianshu].v=v;
	head[u]=bianshu;
	return;
} 

queue <int> q;//bfs用
 
int dep[MAXN];//每个点的深度 

void bfs(int s,int depth)//求father 
{
	q.push(s);
	dep[s]=depth;
	while(!q.empty())
	{
		int ppp=q.front();
		q.pop();
		for(int i=head[ppp];i;i=g[i].next)//遍历 
		{
			if(!visited[g[i].v])
			{
				visited[g[i].v]=true;
				father[g[i].v]=ppp;
				dep[g[i].v]=dep[ppp]+1;//存储深度，比父亲节点深度大1 
				q.push(g[i].v);
			}
		}
	}
}

int jump[MAXN][35];//定义：j[a][b]为a号点往根节点方向走(1<<b)次后的节点编号 

int main()
{
	int n,q,s;
	int uu,vv;
	int a,b;
	int tmp;//深度差 
	
	scanf("%d%d",&n,&q);//有时候需要读入s 
	s=1; 
	
	for(int i=1;i<=n-1;++i)
	{
		scanf("%d%d",&uu,&vv);
		addedge(uu,vv);
		addedge(vv,uu);
	}//加边 
	
	father[s]=0;//注意：father[根]一定要设为0，否则后面跳跃时出问题 
	visited[s]=true;
	bfs(s,1);//求father数组 
	
	for(int i=1;i<=n;++i)
	{
		jump[i][0]=father[i];
	}//jump初值 
	for(int j=1;j<=30;++j)
	{
		for(int i=1;i<=n;++i)
		{
			jump[i][j]=jump[jump[i][j-1]][j-1];
		}
	}//初始化jump数组 
	 
	while(q--)//操作 
	{
		scanf("%d%d",&a,&b);
		
		tmp=(dep[a]>dep[b]?dep[a]-dep[b]:dep[b]-dep[a]);//深度差值 
		
		if(dep[a]>dep[b]) //每次判断是否跳跃(1<<k)次，跳跃到同一深度 
		{
			for(int k=30;k>=0;--k)
			{
				if(tmp>=(1<<k))
				{
					a=jump[a][k];
					tmp-=(1<<k);
				}
			} 
		}
		else if(dep[b]>dep[a]) 
		{
			for(int k=30;k>=0;--k)
			{
				if(tmp>=(1<<k))
				{
					b=jump[b][k];
					tmp-=(1<<k);
				}
			} 
		}//使得a,b位于同一深度 
		
		if(a==b)//跳到同一个点，即LCA就是当前的点，需要特判。 
		{
			printf("%d\n",a);
			continue;
		}
		for(int k=30;k>=0;--k)
		{
			if((jump[a][k]^jump[b][k]))//异或符号^在此处等价于！= 符号 
			{
				a=jump[a][k];
				b=jump[b][k];
			}
		}//跳2的k次方次
		 
		printf("%d\n",father[a]);
	}
	return 0;
}
            • 1
              @ 2024-9-14 17:58:04

              LCA，最近公共祖先问题。

              给定一颗有根树，若节点 k 既是节点 x 的祖先，又是节点 y 的祖先，则称 k 是 \lbrack x, y \rbrack 的公共祖先。在 \lbrack x, y \rbrack 的所有公共祖先中，深度最大的称为最近公共祖先，记作 LCA⁡(x,y)\operatorname*{LCA}(x, y)。

              LCA⁡(x,y)\operatorname*{LCA}(x, y) 即为节点 x→1x \rightarrow 1 和节点 y→1y \rightarrow 1 的第一个中途交汇点。

              因为讲解倍增，所以这里使用 树上倍增法 求解。

              设 fx,kf_{x, k} 表示从 xx 节点走 2k2^k 步到达的祖先节点，若此节点不存在则设 fx,k=0f_{x, k} = 0；显然，fx,0f_{x, 0} 就是 xx 的父节点。

              神奇小公式：$\text{if } k \in \lbrack 1, \log n \rbrack, f_{x, k} = f_{f_{x, k - 1}, k - 1}$

              要解决这个问题，我们还要求出每个节点的深度，可以使用 dfs 解决。

              在处理 LCA 时，我们以 [x,y]\lbrack x, y \rbrack 中深度较大的开始，先使深度较大的缩短到最接近另一个深度的节点（自己 / 最近的祖先），然后一直向上即可。

              完整代码：

              #include <bits/stdc++.h>
#define int long long
#define il inline
using namespace std;

il int read()
{
    int x = 0;
	char c = getchar();
    while (c < '0')
		c = getchar();
    while (c >= '0')
	{
		x = x * 10 + (c - '0');
		c = getchar();
	}    
    return x;
}

int n, m, s;
vector<int> edge[500005];
int lca[500005][25], dep[500005];
void dfs(int x, int fa)
{
    lca[x][0] = fa;
    dep[x] = dep[fa] + 1;
    int now = edge[x].size();
    for (int i = 0; i < now; i++)
    {
        if (edge[x][i] == fa)
			continue;
        dfs(edge[x][i], x);
    }
    return ;
}
void pre()
{
    for (int j = 1; j <= 20; j++)
    {
        for (int i = 1; i <= n; i++)
            lca[i][j] = lca[lca[i][j - 1]][j - 1];
    }
    return ;
}
il int LCA(int x, int y)
{
    if (dep[x] < dep[y])
		swap(x, y);
    for (int i = 20; i >= 0; i--)
    {
        if (dep[lca[x][i]] >= dep[y])
            x = lca[x][i];
    }
    if (x == y)
		return x;
    for (int i = 20; i >= 0; i--)
    {
        if (lca[x][i] != lca[y][i])
            x = lca[x][i], y = lca[y][i];
    }
    return lca[x][0];
}
signed main()
{
    n = read(); m = read(); s = read();
    for (int i = 1; i < n; i++)
    {
    	int x, y;
        x = read(); y = read();
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    dfs(s, 0);
    pre();
    for (int i = 1; i <= m; i++)
    {
    	int x, y;
        x = read(); y = read();
        cout << LCA(x, y) << "\n";
    }
    return 0;
}

              时间复杂度：O(qlog⁡n)O(q \log n)。

              • 1
                @ 2024-6-30 10:43:54

                深度 depdep。

                深度最大的公共祖先。

                1. 先把 xx 的祖先进行标记，再让 yy 一路往上遍历祖先，第一个碰到的被 xx 标记过得祖先即为最近公共祖先，复杂度 O(n)O(n)。
                int LCA(int x, int y) {
	memset(vis, 0, sizeof(vis));
	while (x != 0) {
		vis[x] = 1;
		x = fa[x];
	}
	while (vis[y] == 0) {
		y = fa[y];
	}
	return y;
}
                1. 两个点同时走，移动到一个深度，然后同时往上走，直到碰到的时候，就找到了。
                void dfs(int u) {//深度
	dep[u] = dep[fa[u]] + 1;
	for (int i = head[u]; i != -1; i = E[i].next) {//链式前向星
		int v = E[i].v;
		if (v != fa[u]) {
			fa[v] = u;
			dfs(v);
		}
	}
}

int LCA(int x, int y) {
	if (dep[x] < dep[y]) {
		swap(x, y);
	}
	while (dep[x] > dep[y]) {
		x = fa[x];
	}
	while (x != y) {
		x = fa[x];
		y = fa[y];
	}
	return x;
}
                1. 以二进制的方式往上跳。

                求出 2K≤dep[x]2^K \le dep[x]。

                int K = 0;
while ((1 << (K + 1)) <= dep[x]) {
	K++;
}
for (int i = K; i >= 0; i--) {
	//如果 x 的 2 ^ i 的祖先深度 >= dep[y]，那么就让 x 跳到 2 ^ i 这个祖先的位置。
	
}

                设 len=dep[x]−dep[y]len = dep[x] - dep[y]，那么 lenlen 的二进制下中的 11 的位置就表示 xx 要跳 2i2^i 步，因为方案是唯一的，所以从大到小凑，一定不会错。

                如果 dep[x]+2i≥dep[y]dep[x] + 2^i \ge dep[y]，那么 2i2^i 这一步是必须跳的。

                如果这一步不跳，那就永远不能跳到 dep[y]dep[y]。

                2i>2i−1+2i−2+⋯+202^i > 2^{i - 1} + 2^{i - 2} + \dots + 2^0。

                任意整数都可以被表示成多个不同的二进制幂次数字之和。

                表示方式是唯一的。

                1. 状态：fa[i][j]fa[i][j] 表示 ii 的距离为 2j2^j 的祖先是谁。
                2. 状态转移方程：fa[i][j]=fa[fa[i][j−1]][j−1]fa[i][j] = fa[fa[i][j - 1]][j - 1]。

                ii 的 2j2^j 的祖先其实就是 ii 的 2j−12^{j - 1} 祖先的 2j−12^{j - 1}。

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


typedef long long ll;
int n, q, F;
int d[600005];
int fa[600005][25];

int head[600005];
struct Node {
    int v, nex;
} e[12000005]; 
int ecnt;
void add(int u, int v) {
    ecnt++;
    e[ecnt].v = v;
    e[ecnt].nex = head[u];
    head[u] = ecnt;
}

void dfs(int father, int root) {
    d[root] = d[father] + 1;
    fa[root][0] = father;
    for (int i = 1; i <= 19; i++) {
        fa[root][i] = fa[fa[root][i - 1]][i - 1];
    }
    for (int i = head[root]; i != 0; i = e[i].nex) {
        int v = e[i].v;
        if (v != father) {
            dfs(root, v);
        }
    }
    return;
}

int LCA(int x, int y) {
    if (d[x] < d[y]) { 
        swap(x, y);
    }
    for (int i = 19; i >= 0; i--) {
        if (d[fa[x][i]] >= d[y]) {
            x = fa[x][i];
        }
    }
    if (x == y) {
        return x;
    }
    for (int i = 19; i >= 0; i--) {
        if (fa[x][i] != fa[y][i]) {
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    return fa[x][0];
}

int main() {
    cin >> n >> q;
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }
    dfs(0, 1);
    while (q--) {
        int a, b;
        cin >> a >> b;
        cout << LCA(a, b) << "\n";
    }
    return 0;
}
                • 0
                  @ 2025-10-7 20:13:01

                  int Graph; cin>>Graph; pair<int,int> ask; cin>>ask; cout<<lca(ask);

                  • 0
                    @ 2025-7-9 14:43:51

                    #include #include #include #include using namespace std;

                    const int MAXN = 5e5 + 5; const int LOG = 20;

                    vector adj[MAXN]; int parent[MAXN][LOG]; int depth[MAXN];

                    void bfs(int root) { queue q; q.push(root); depth[root] = 0; parent[root][0] = -1; // 标记根节点的父节点为-1

                    while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int v : adj[u]) {
        if (v != parent[u][0]) {
            depth[v] = depth[u] + 1;
            parent[v][0] = u;
            q.push(v);
        }
    }
}

                    }

                    void preprocess(int n) { for (int j = 1; j < LOG; ++j) { for (int i = 1; i <= n; ++i) { if (parent[i][j-1] != -1) { parent[i][j] = parent[parent[i][j-1]][j-1]; } else { parent[i][j] = -1; } } } }

                    int lca(int u, int v) { if (depth[u] < depth[v]) { swap(u, v); } // 提升u到v的深度 for (int j = LOG - 1; j >= 0; --j) { if (depth[u] - (1 << j) >= depth[v]) { u = parent[u][j]; } } if (u == v) { return u; } // 现在u和v在同一深度，一起向上找 for (int j = LOG - 1; j >= 0; --j) { if (parent[u][j] != -1 && parent[u][j] != parent[v][j]) { u = parent[u][j]; v = parent[v][j]; } } return parent[u][0]; }

                    int main() { ios::sync_with_stdio(false); cin.tie(nullptr);

                    int n, q;
cin >> n >> q;

for (int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
}

// 初始化根节点的父节点为-1
bfs(1);
preprocess(n);

while (q--) {
    int x, y;
    cin >> x >> y;
    cout << lca(x, y) << '\n';
}

return 0;

                    }

                    • -2
                      @ 2024-8-18 14:50:42

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

                      const int MAXN=500000+5; const int MAXM=500000+5;

                      int head[MAXN]; int father[MAXN]; bool visited[MAXM]; int bianshu;

                      struct edge { int v,next; }g[2*MAXM];

                      void addedge(int u,int v) { g[++bianshu].next=head[u]; g[bianshu].v=v; head[u]=bianshu; return; }

                      queue q; int s; void bfs() { q.push(s); while(!q.empty()) { int ppp=q.front(); q.pop(); for(int i=head[ppp];i;i=g[i].next) { if(!visited[g[i].v]) { visited[g[i].v]=true; father[g[i].v]=ppp; q.push(g[i].v); } } }

                      }

                      int path1[MAXN]; int path2[MAXN]; int cntp1,cntp2; int ans; int main() { int n,q; int uu,vv; int a,b; int LCA,a1,a2; scanf("%d%d%d",&n,&q,&s); for(int i=1;i<=n-1;++i) { scanf("%d%d",&uu,&vv); addedge(uu,vv); addedge(vv,uu); } father[s]=s; visited[s]=true; bfs(); for(int i=1;i<=q;++i) { scanf("%d%d",&a,&b); for(int j=a;j!=s;j=father[j]) { path1[++cntp1]=j; } path1[++cntp1]=s; for(int j=b;j!=s;j=father[j]) { path2[++cntp2]=j; } path2[++cntp2]=s; while(path1[cntp1--]==path2[cntp2--]) { ans=path1[cntp1+1]; } printf("%d\n",ans); memset(path1,0,sizeof(path1)); memset(path2,0,sizeof(path2)); cntp1=0; cntp2=0; ans=0; } return 0; }

                      • -6
                        @ 2022-1-22 22:11:04 
                        #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct zzz {
    int t, nex;
}e[500010 << 1]; int head[500010], tot;
void add(int x, int y) {
	e[++tot].t = y;
	e[tot].nex = head[x];
	head[x] = tot;
}
int depth[500001], fa[500001][22], lg[500001];
void dfs(int now, int fath) {
	fa[now][0] = fath; depth[now] = depth[fath] + 1;
	for(int i = 1; i <= lg[depth[now]]; ++i)
		fa[now][i] = fa[fa[now][i-1]][i-1];
	for(int i = head[now]; i; i = e[i].nex)
		if(e[i].t != fath) dfs(e[i].t, now);
}
int LCA(int x, int y) {
	if(depth[x] < depth[y]) swap(x, y);
	while(depth[x] > depth[y])
		x = fa[x][lg[depth[x]-depth[y]] - 1];
	if(x == y) return x;
	for(int k = lg[depth[x]] - 1; k >= 0; --k)
		if(fa[x][k] != fa[y][k])
			x = fa[x][k], y = fa[y][k];
	return fa[x][0];
}
int main() {
	int n, m, s = 1; scanf("%d%d", &n, &m);
	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;
}
                        • -7
                          @ 2021-11-6 16:57:08

                          题目描述 如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。

                          输入格式 第一行包含三个正整数N、M、S，分别表示树的结点个数、询问的个数和树根结点的序号。

                          接下来N-1行每行包含两个正整数x、y，表示x结点和y结点之间有一条直接连接的边（数据保证可以构成树）。

                          接下来M行每行包含两个正整数a、b，表示询问a结点和b结点的最近公共祖先。

                          输出格式 输出包含M行，每行包含一个正整数，依次为每一个询问的结果。

                          输入输出样例 输入 #1复制

                          5 5 4 3 1 2 4 5 1 1 4 2 4 3 2 3 5 1 2 4 5 输出 #1复制

                          4 4 1 4 4 说明/提示 时空限制：1000ms,128M

                          数据规模：

                          对于30%的数据：N<=10，M<=10

                          对于70%的数据：N<=10000，M<=10000

                          对于100%的数据：N<=500000，M<=500000

                          样例说明：

                          该树结构如下：

                          第一次询问：2、4的最近公共祖先，故为4。

                          第二次询问：3、2的最近公共祖先，故为4。

                          第三次询问：3、5的最近公共祖先，故为1。

                          第四次询问：1、2的最近公共祖先，故为4。

                          第五次询问：4、5的最近公共祖先，故为4。

                          故输出依次为4、4、1、4、4。

                          做这个题之前，刚学了树链剖分，这就用上了，求最近公共祖先（LCA）其实就是用树链剖分后，进行简单的链查询即可（让那两个结点的指针中所处链的顶端结点深度小的（也就是靠下的那条链）的指针不断向上跳啊，跳啊。。。直到两指针在同一条链时返回深度较小的那个指针所指的结点编号（即为LCA）即可）。

                          完整代码：

                          #include #include #include #include #define int long long using namespace std; const int maxn=5e5+5; typedef struct Edge { int next,to; }edg; edg e[maxn<<1]; int n,m,s,cnt,head[maxn<<1];

                          void AddEdge(int u,int v) { e[cnt].to=v; e[cnt].next=head[u]; head[u]=cnt++; }

                          int fa[maxn],son[maxn],depth[maxn],siz[maxn]; void dfs1(int u,int f) { fa[u]=f; depth[u]=depth[f]+1; siz[u]=1; int maxsize=-1; for(int i=head[u];~i;i=e[i].next) { int v=e[i].to; if(v==f) continue; dfs1(v,u); siz[u]+=siz[v]; if(siz[v]>maxsize) { maxsize=siz[v]; son[u]=v; } } }

                          int tim,dfn[maxn],top[maxn]; void dfs2(int u,int t) { dfn[u]=++tim; top[u]=t; if(!son[u]) return; dfs2(son[u],t); for(int i=head[u];~i;i=e[i].next) { int v=e[i].to; if(vfa[u]||vson[u]) continue; dfs2(v,v); } }

                          int query(int x,int y) { while(top[x]!=top[y]) { if(depth[top[x]]<depth[top[y]]) swap(x,y); x=fa[top[x]]; } if(depth[x]>depth[y]) swap(x,y); return x; }

                          signed main() { // ios::sync_with_stdio(false); // cin.tie(0); memset(head,-1,sizeof(head)); scanf("%lld%lld%lld",&n,&m,&s); int N=n-1; while(N--) { int u,v; scanf("%lld%lld",&u,&v); AddEdge(u,v); AddEdge(v,u); } dfs1(s,s); dfs2(s,s); while(m--) { int x,y; scanf("%lld%lld",&x,&y); int ans=query(x,y); cout<<ans<<endl; } }

                          • -24
                            @ 2021-9-21 19:19:45

                            az

                          • 1

                          【模板】最近公共祖先

                          Information

                          ID
                          121
                          Time
                          2000ms
                          Memory
                          256MiB
                          Difficulty
                          6
                          Tags
                          # Submissions
                          854
                          Accepted
                          258
                          Uploaded By
                          1. Language
                          2. Legacy mode
                          3. Theme
                          2. © 2021-2026 Hydro.ac
                          4. Worker 1, 44ms
                          5. Hydro v5.0.0-beta.18-ae60a99-dirty Professional