0%

倍增求最近公共祖先

发表于 更新于 分类于
利用倍增思想进行满log稳定查找lca

如何求最近公共祖先？

朴素的想法:$dfs_1$标记深度，深度大的先跳到与深度小的一级，再同时向上跳，直到找到$LCA$。

怎么形容呢？一个字：那是真的 慢 的要飞起

怎么办？考虑大步流星的跳：倍增。

倍增的过程，就是每次跳$2^?$深度，就能把效率提高到$\log$级。

怎么实现？类似动规思想，用$f[i][j]$来表示$i$的第$2^j$辈祖先。

小小的特判：$f[i][0]$系$i$父结点，而不存在的节点记为$f[i][j]=0$。

$Caution!$ 由于$2^{k-1}+ 2^{k-1}=2^k$

所以有递推式：

$f[i][j]=\begin{cases}f[f[i][j-1]][j-1]&1\leqslant j\leqslant \log{n} \fa[i]&j=0\end{cases}$

预处理复杂度O($nlogn$)；

怎么查询？

  • 交换两个变量的值，保证前者深度大，便于操作。

  • 拆分步数，试着走$2^{logn}$到$2^0$步，如果走完之后深的点还是深，则把此点更新到他上一步走到的那个祖先处

  • 单方面调整后，如果二者到达同一深度已经满足找到$LCA$，那么结束，否则调整两个点同上试探性倍增，保持深度一致并$while$不相遇于$LCA$时继续。

  • $while$结束后，取出当下的父结点f[i][0]，即二者$LCA$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
#define ri register int
using namespace std;
const int maxn=20031125;
int dep[maxn];
struct edge
{
	int to;
	int nex;
	int val;
}e[maxn];
itn f[maxn];
void init(int u,int fa)
{
	int _ceil=19;//这就够了2^20=1048576
	dep[u]=dep[fa]|1;//+1=|1
	for(ri i=0;i<=_ceil;i++)
	{
		f[u][i+1]=f[f[u][i]][i];//父子递推
	}
	for(ri i=head[u];i;i=e[i].nex)
	{
		int to=e[i].to;
		if(to==fa)
		{
			continue;
		}
		else
		{
			f[to][0]=u;//定义父子关系
			init(to,u);
		}
	}
}

int lca(int x,int y)
{
	if(dep[x]<dep[y])
	{
		swap(x,y);//调整深度
	}
	for(ri i=20;i>=0;i--)
	{
		if(dep[f[x][i]]>dep[y])
		{
			x=f[x][i];//jmp
		}
		if(x==y)
		{
			return x;
		}
	}//单方面倍增至同深度
	for(ri i=20;i>=0;i--)
	{
		if(f[x][i]!=f[y][i])
		{
			x=f[x][i];
			y=f[y][i];
		}
	}//同时倍增
	return f[x][0];//找汇合点前的点的父亲即LCA
}

查询复杂度O($logn$)

例题：LuoGu3884:二叉树问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
//lca求法
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
int n,m;

struct Edge
{
	int v;
	int nex;
} e[maxn*2];

int head[maxn],dep[maxn],f[maxn][21];


int cnt=0;

void add(int u,int v)
{
	e[++cnt].v=v;
	e[cnt].nex=head[u];
	head[u]=cnt;
}

void dfs(int u,int fa)
{
	dep[u]=dep[fa]+1;
	f[u][0]=fa;
	
	for(int i=1; (1<<i)<=dep[u]; i++)
	{
		f[u][i]=f[f[u][i-1]][i-1];
	}
	for(int i=head[u]; i!=-1; i=e[i].nex)
	{
		int v=e[i].v;
		if(v!=fa)
		{
			dfs(v,u);
		}
	}
}
int lca(int x,int y)
{
	if(dep[x]>dep[y])
	{
		swap(x,y);
	}
	for(int i=20; i>=0; i--)
	{
		if(dep[x]<=dep[y]-(1<<i))
		{
			y=f[y][i];
		}
	}
	if(x==y)
	{
		return x;
	}
	for(int i=20; i>=0; i--)
	{
		if(f[x][i]==f[y][i])
		{
			continue;
		}
		else
		{
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];
}
struct Tree
{
	int right;
	int left;
	int fa;
	int dep;
	int data;
} t[25000];
int x,y,ans,sum[1000];
int main()
{
	memset(head,-1,sizeof(head));
	scanf("%d",&n);
	t[1].dep=1;
	t[1].fa=0;
	for(int i=1; i<=n-1; i++)
	{
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
		if(t[x].left==0)
		{
			t[x].left=y;
		}
		else
		{
			t[x].right=y;
		}
		t[y].fa=x;
		t[y].dep=t[x].dep+1;
		if(t[y].dep>ans)
		{
			ans=t[y].dep;
		}
	}
	dfs(1,0);
	for(int i=1; i<=n; i++)
	{
		sum[t[i].dep]++;
	}
	sort(sum+1,sum+1+n);
	cout<<ans<<endl;
	cout<<sum[n]<<endl;
	int a,b;
	scanf("%d%d",&a,&b);
	int res=lca(a,b);
	cout<<(t[a].dep-t[res].dep)*2+t[b].dep-t[res].dep;//距离
}