倍增求LCA模板

　

LCA

1.引入

点击转入模板题，by-luogu

2.思路

这道题目是倍增求LCA的模板题。

首先，大家都知道LCA的定义吧？（两个节点的公共父节点）如果我们求两个点的LCA的使用暴力求解（DFS找出要求点的深度，一个一个往上跳，一次一次查询），在卡时间的竞赛中是肯定会炸掉的。那么，我们就使用另一种方法，树上倍增法：

我们设 表示  的  倍祖先,那么很容易知道，就是当前节点的父亲（记住，当前节点可以代表当前深度的所有节点因为它是一颗树！），就是当前节点的父亲的父亲也就是 ,  就是当前节点的父亲的父亲的父亲，也就是也等于...（以此类推）.那么，我们就可以计算出当前节点到它所有的父亲要走的路（因为它是一棵树）。片段是这样的：

inline void dfs(int now,int fath)
{
	depht[now]=depht[fath]+1;
	father[now][0]=fath;
	for(register int i=1;(1<<i)<=depht[now];++i)
	  father[now][i]=father[father[now][i-1]][i-1];//求出当前节点到各个祖先节点的距离。
	for(register int i=head[now];i;i=e[i].nex)
	{
		if(e[i].t!=fath)//要求的这一条边不能通往父亲节点
        dfs(e[i].t,now);//求出指向当前节点的子节点到各个祖先节点的距离（有点绕）
	}	
}

基于father数组我们可以计算LCA了。

我们先设 depth[x] 和 depth[y] 为当前节点的深度，那么，基于二进制拆分的思想，把x,y调到同一深度。

之后，我们又运用二进制拆分的思想，让他们一起走到同一个点。（尝试走2^(log（depth[x]-depth[y]）（向下取整）)步，2^(log（depth[x]-depth[y]-1）（向下取整）)步....1步）

不说了，上代码：

#include<bits/stdc++.h>
using namespace std;
struct node{
	int t,nex;
}e[500001<<1];
int depht[500001],father[500001][22],lg[500001],head[500001];
int tot;
inline void add(int x,int y)
{
	e[++tot].t=y;
	e[tot].nex=head[x];
	head[x]=tot;
}
inline void dfs(int now,int fath)
{
	depht[now]=depht[fath]+1;
	father[now][0]=fath;
	for(register int i=1;(1<<i)<=depht[now];++i)
	  father[now][i]=father[father[now][i-1]][i-1];
	for(register int i=head[now];i;i=e[i].nex)
	{
		if(e[i].t!=fath)dfs(e[i].t,now);	
	}	
}
inline int lca(int x,int y)
{
	if(depht[x]<depht[y])
	  swap(x,y);
	while(depht[x]>depht[y])
	  x=father[x][lg[depht[x]-depht[y]]-1];
	if(x==y)
	  return x;
	for(register int k=lg[depht[x]];k>=0;--k)
	  if(father[x][k]!=father[y][k])
	    x=father[x][k],y=father[y][k];
	return father[x][0];
}
int n,m,s;
int main()
{
	//freopen("1.txt","r",stdin);
	scanf("%d%d%d",&n,&m,&s);
	for(register int i=1;i<=n-1;++i)
	{
		int x,y;scanf("%d%d",&x,&y);
		add(x,y);add(y,x);
	}
	dfs(s,0);
	for(register int i=1;i<=n;++i)
	  lg[i]=lg[i-1]+(1<<lg[i-1]==i);
	for(register int i=1;i<=m;++i)
	{
		int x,y;scanf("%d%d",&x,&y);
		printf("%d\n",lca(x,y));
	}
	return 0;
}

相关阅读