本题的核心思路：倍增。 如果暴力求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;
}

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

tg重点知识点：LCA

文件头

求LCA的基本方式：

1. 在线法

代表：倍增，rmq

这里介绍倍增法。

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

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

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

核心代码：

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)$

2. 离线法

代表：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)$。

来点不一样的，用树链剖分求LCA。 先把树剖成链，记录每个点$u$所在链的最顶端节点 $top_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;
}

倍增法求 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;
}

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

很模板的一道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;
}

#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;

}

#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;
}

LCA，最近公共祖先问题。

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

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

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

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

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

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

在处理 LCA 时，我们以 $\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(q \log n)$。

深度 $dep$。

深度最大的公共祖先。

1. 先把 $x$ 的祖先进行标记，再让 $y$ 一路往上遍历祖先，第一个碰到的被 $x$ 标记过得祖先即为最近公共祖先，复杂度 $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;
}

2. 两个点同时走，移动到一个深度，然后同时往上走，直到碰到的时候，就找到了。

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;
}

3. 以二进制的方式往上跳。

求出 $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$ 的二进制下中的 $1$ 的位置就表示 $x$ 要跳 $2^i$ 步，因为方案是唯一的，所以从大到小凑，一定不会错。

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

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

$2^i > 2^{i - 1} + 2^{i - 2} + \dots + 2^0$。

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

表示方式是唯一的。

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

$i$ 的 $2^j$ 的祖先其实就是 $i$ 的 $2^{j - 1}$ 祖先的 $2^{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;
}

#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; }

#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;
}

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

输入格式 第一行包含三个正整数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; } }

az