必威体育Betway必威体育官网
当前位置:首页 > IT技术

倍增求LCA模板

时间:2019-08-18 00:11:03来源:IT技术作者:seo实验室小编阅读:77次「手机版」
 

LCA

1.引入

点击转入模板题,by-luogu

2.思路

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

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

我们设father[x,k] 表示 x 的 2^k 倍祖先,那么很容易知道,father[x,0]就是当前节点的父亲(记住,当前节点可以代表当前深度的所有节点因为它是一颗树!),father[x,1]就是当前节点的父亲的父亲也就是fatehr[father[x,0],0] ,  father[x,2]就是当前节点的父亲的父亲的父亲,也就是father[father[father[x,0],0],0]也等于father[father[x,1],1]...(以此类推).那么,我们就可以计算出当前节点到它所有的父亲要走的路(因为它是一棵树)。片段是这样的:

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

相关阅读

分享到:

栏目导航

推荐阅读

热门阅读