Criska

LCA（最近公共祖先）

• 分类: LCA • 标签: LCA

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1000010;
int n,m,s,tope,head[N],f[N][20],log2n,dep[N];
struct node{
	int to,next;
}e[N];
void intt(int x,int y)
{
	tope++;
	e[tope].to=y;
	e[tope].next=head[x];
	head[x]=tope;
}
inline void dfs(int x)
{
	for(int i=head[x],y=e[i].to;i;i=e[i].next,y=e[i].to)
	{
		if(f[x][0]==y) continue;
		f[y][0]=x;
		dep[y]=dep[x]+1;
		dfs(y);
	}
}
inline int log2(int x)
{
	int r;
	for(r=0;(1<<r)<=x;++r);
	return r-1;
}
inline int lca(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=log2n;i>=0;--i)
		if(dep[f[x][i]]>=dep[y])
			x=f[x][i];
	if(x==y) return x;
	for(int i=log2n;i>=0;--i)
		if(f[x][i]!=f[y][i])
		{
			x=f[x][i];
			y=f[y][i];
		}
	return f[x][0];
}
int main()
{
	scanf("%d%d%d",&n,&m,&s);
	dep[s]=1;
	log2n=log2(n);
	for(int i=1;i<=n-1;++i)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		intt(x,y);
		intt(y,x);
	}
	dfs(s);
	
	for(int i=1;i<=log2n;++i)
		for(int j=1;j<=n;++j)
			f[j][i]=f[f[j][i-1]][i-1];
	for(int i=1;i<=m;++i)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		int l=lca(x,y);
		printf("%d\n",l);
	}
	
	return 0;
}

【例题】过路费

【问题描述】

在某个遥远的国家里，有 n个城市。编号为 1,2,3,…,n。这个国家的政府修
建了m 条双向道路，每条道路连接着两个城市。政府规定从城市 S 到城市T需
要收取的过路费为所经过城市之间道路长度的最大值。如：A到B长度为 2，B
到C 长度为3，那么开车从 A经过 B到C 需要上交的过路费为 3。
佳佳是个做生意的人，需要经常开车从任意一个城市到另外一个城市，因此
他需要频繁地上交过路费，由于忙于做生意，所以他无时间来寻找交过路费最低
的行驶路线。然而， 当他交的过路费越多他的心情就变得越糟糕。 作为秘书的你，
需要每次根据老板的起止城市，提供给他从开始城市到达目的城市，最少需要上
交多少过路费。

【输入文件】

第一行是两个整数 n 和m，分别表示城市的个数以及道路的条数。
接下来 m 行，每行包含三个整数 a，b，w（1≤a，b≤n，0≤w≤10^9），表示
a与b之间有一条长度为 w的道路。
接着有一行为一个整数 q，表示佳佳发出的询问个数。
再接下来 q行，每一行包含两个整数 S，T（1≤S,T≤n，S≠T）, 表示开始城
市S 和目的城市T。

【输出文件】

输出文件共q行，每行一个整数，分别表示每个询问需要上交的最少过路费
用。输入数据保证所有的城市都是连通的。

  • 即为给定任意点对，求所有两点之间可连接两点的路径中的最大边最小值。二分的思想是显而易见的，但是只能得30分。

  • 仔细分析一下题目，会发现如果要任意两点之间的路径中最大边最小，整个图便符合了最小生成树性质！！
    证明如下：
    若存在从a到b的一条比最小生成树上连接a与b的所经过路径上边更小的边c，则将c加入最小生成树中可得到一个更小的生成树，这显然不符合最小生成树的定义，故不存在这样的边c。
    其实最小生成树克鲁斯卡尔算法的思想就是按照选择两点之间权值最小的边来构建的。

  • 大概算法就出来了，读入数据，克鲁斯卡尔算法求最小生成树，但这时会发现一个严重问题：怎样处理询问？n的范围过大，dist[n][n]无法存储，枚举根节点来dfs求到任意节点的答案，则算法时间上升到O(n^2)，只能得30分。再分析一下，对于一棵以任一结点为根的已经建好的最小生成树，此时询问无非是两种情况 1：两个节点为直系祖先关系，可直接求得解。2：两个节点为不同分枝上的节点。求这两个节点的答案难以相出好办法。但可以知道两个节点之间只存在唯一一条简单路径，这条唯一简单路径上的变的最大值即为答案，且这两个结点的最近公共最先必然在这一点上。想到可以转化为LCA算法，dfs一边，当处理完当前节点所有的子节点后开始回答关于这个节点的问题。

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
122
123
124
125
126
127
128
129
130
131
132
133
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=200000;
int tot,k,father[N],n,m,f[N][20],log2n;
int tope,head[N],dep[N],cost[N];
struct node{
	int xx,yy,zz;
}c[N];
struct node1{
	int next,to,w;
}e[N];
void intt(int x,int y,int z)
{
	tope++;
	e[tope].next=head[x];
	e[tope].to=y;
	e[tope].w=z;
	head[x]=tope;
}
int comp(const node & a,const node & b)
{
	return a.zz<b.zz;
}
int fa(int x)
{
	if(father[x]!=x)
	father[x]=fa(father[x]);
	return father[x];
}
void un(int r1,int r2)
{
	father[r2]=r1;
}
inline void dfs(int x)
{
	for(int i=head[x],y=e[i].to;i;i=e[i].next,y=e[i].to)
	{
		if(f[x][0]==y) continue;//shuang xiang bian fang zhi sou hui qu haha
		f[y][0]=x;
		dep[y]=dep[x]+1;
		cost[y]=e[i].w;
		dfs(y);
	}
}
inline int log2(int x)
{
	int r;
	for(r=0;(1<<r)<=x;++r);
	return r-1;
}
inline int lca(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=log2n;i>=0;--i)
		if(dep[f[x][i]]>=dep[y])
			x=f[x][i];
	if(x==y) return x;
	for(int i=log2n;i>=0;--i)
		if(f[x][i]!=f[y][i])
		{
			x=f[x][i];
			y=f[y][i];
		}
	return f[x][0];
	
}
int main()
{
	freopen("cost.in","r",stdin);
	freopen("cost.out","w",stdout);	
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		c[i].xx=x;c[i].yy=y;c[i].zz=z;
	}
	k=0;
	log2n=log2(n);
	for(int i=1;i<=n;++i)
		father[i]=i;
	sort(c+1,c+m+1,comp);
	for(int i=1;i<=m;++i)
	{
		int x=c[i].xx,y=c[i].yy,z=c[i].zz;
		int r1=fa(x),r2=fa(y);
		if(r1!=r2)
		{
			un(r1,r2);
			intt(x,y,z);
			intt(y,x,z);
			k++;
		}
		if(k==n-1) break;
	}
	dfs(1);
	for(int j=1;j<=log2n;++j)
		for(int i=1;i<=n;++i)
			f[i][j]=f[f[i][j-1]][j-1];
	int q;
	scanf("%d",&q);
	for(int i=1;i<=q;++i)
	{
		int x,y,ans=0;
		scanf("%d%d",&x,&y);
		int fa=lca(x,y);
		while(x!=fa)
		{
			if(ans<cost[x]) ans=cost[x];
			x=f[x][0];
		}
		while(y!=fa)
		{
			if(ans<cost[y]) ans=cost[y];
			y=f[y][0];
		}	
		printf("%d\n",ans);	
	}
	return 0;
}

【例题】货车运输

  • 超级坑爹的例题……哭晕……调了一个晚上……LCA不难理解，但是当加上最小生成树和倍增和其他balabala的东西时就会特别难调，所以要有（可能永远也调不出的）思想准备和越挫越勇的耐心。
  • 以上都是我在胡说八道，其实这道题和上一个例题挺像的，但是有一点点不一样（我到最后才发现╭(╯^╰)╮），给个忠告，认真审题。

附上垃圾代码

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
122
123
124
125
126
127
128
129
130
131
132
133
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=500010;
int n,m,s,tope,head[N],f[N][30],dep[N],nn,fa[N],cost[N];
struct node{
	int to,next,w;
	int xx,yy,zz;
}e[N];
inline int find(int x)
{
	if(x!=fa[x]) fa[x]=find(fa[x]);
	return fa[x];
}
int comp(const node & a,const node & b)
{
	return a.zz>b.zz;
}
void un(int r1,int r2)
{
	fa[r2]=r1;
}
inline void intt(int x,int y,int z)
{
	tope++;
	e[tope].to=y;
	e[tope].next=head[x];
	e[tope].w=z;
	head[x]=tope;
}
inline void dfs(int x)
{
	for(int i=head[x],y=e[i].to;i;i=e[i].next,y=e[i].to)
	{
		if(f[x][0]==y) continue;
		f[y][0]=x;
		dep[y]=dep[x]+1;
		cost[y]=e[i].w;
		dfs(y);
	}
}
inline int log2(int x)
{
	int r;
	for(r=0;(1<<r)<=x;++r);
	return r-1;
}
inline int lca(int a,int b)
{
	if(dep[a]<dep[b]) swap(a,b);
	for(int i=nn;i>=0;--i)
		if(dep[f[a][i]]>=dep[b])
			a=f[a][i];
	if(a==b) return a;
	for(int i=nn;i>=0;--i)
		if(f[a][i]!=f[b][i])
		{
			a=f[a][i];
			b=f[b][i];
		}
	return f[a][0];
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		e[i].xx=x;e[i].yy=y;e[i].zz=z;
	}
	int k=0;
	for(int i=1;i<=n;++i)
		fa[i]=i;
	sort(e+1,e+m+1,comp);
	for(int i=1;i<=m;++i)
	{
		int x=e[i].xx,y=e[i].yy,z=e[i].zz;
		int r1=find(x),r2=find(y);
		if(r1!=r2)
		{
			un(r1,r2);
			intt(x,y,z);
			intt(y,x,z);
			k++;
		}
		//if(k==n-1) break;
	}
	//dep[1]=1;
	dfs(1);
	nn=log2(n);
	for(int i=1;i<=nn;++i)
		for(int j=1;j<=n;++j)
			f[j][i]=f[f[j][i-1]][i-1];
	int q;
	scanf("%d",&q);
	for(int i=1;i<=q;++i)
	{
		int a,b,ans=999999999;
		scanf("%d%d",&a,&b);
		int r1=find(a),r2=find(b);
		if(r1!=r2) printf("-1\n");
		else
		{
			int ff=lca(a,b);
			while(a!=ff)
			{
				if(ans>cost[a]&&cost[a]!=0) ans=cost[a];
				a=f[a][0];
			}
			while(b!=ff)
			{
				if(ans>cost[b]&&cost[b]!=0) ans=cost[b];
				b=f[b][0];
			}
			
			printf("%d\n",ans);
		}
		
	}
	return 0;
}

【例题】仓鼠找sugar

垃圾读入优化…………再碰我就剁手
改了整整一个多小时，读入优化一去就A了【手动再见】

  • 根据题意，我们可以先把不可能相遇的情况判断一下。设p是a,b的LCA，q是c,d的LCA，如果说一对点的LCA的深度比另外一对点中任意一个点的深度都要深的话则不可能相遇，输出N。

  • 然后，如果不满足上面的条件则继续进行判断，我们假设p的深度大于q的深度，那么，如果可能相遇的话（a或b）与（q）的LCA就是q。q的深度大于p的深度的情况亦然。输出Y。

  • 以上情况都不满足的话，输出N。

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
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=200001;
int tope,head[N],dep[N],f[N][30],n,nn,m,q;
struct node{
	int to,next;
}e[N];
inline int intt(int x,int y)
{
	tope++;
	e[tope].to=y;
	e[tope].next=head[x];
	head[x]=tope;
}
inline int dfs(int x)
{
	for(int i=head[x],y=e[i].to;i;i=e[i].next,y=e[i].to)
	{
		if(f[x][0]==y) continue;
		f[y][0]=x;
		dep[y]=dep[x]+1;
		dfs(y);
	}
}
inline int log2(int x)
{
	int r;
	for(r=0;(1<<r)<=x;++r);
	return r-1;
}
inline int lca(int a,int b)
{
	if(dep[a]<dep[b]) swap(a,b);
	for(int i=nn;i>=0;--i)
		if(dep[f[a][i]]>=dep[b])
			a=f[a][i];
	if(a==b) return a;
	for(int i=nn;i>=0;--i)
		if(f[a][i]!=f[b][i])
		{
			a=f[a][i];
			b=f[b][i];
		}
	return f[a][0];
}
int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n-1;++i)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		intt(x,y);
		intt(y,x);
	}
	dep[1]=1;
	dfs(1);
	nn=log2(n);
	for(int i=1;i<=nn;++i)
		for(int j=1;j<=n;++j)
			f[j][i]=f[f[j][i-1]][i-1];
	for(int i=1;i<=q;++i)
	{
		int a,b,c,d;
		scanf("%d%d%d%d",&a,&b,&c,&d);
		int p,q;
		p=lca(a,b);
		q=lca(c,d);
		if(dep[p]>dep[c]&&dep[p]>dep[d])
		{
			printf("N\n");
			continue;
		} 
		if(dep[q]>dep[a]&&dep[q]>dep[b])
		{
			printf("N\n");
			continue;
		}
		if(dep[p]>=dep[q])//x1
		{
			if(lca(p,c)==p||lca(p,d)==p) 
			{
				printf("Y\n");
				continue;
			}
		}
		else
		{
			if(lca(q,a)==q||lca(q,b)==q) 
			{
				printf("Y\n");
				continue;
			}			
		}
		printf("N\n");
	}
	return 0;
}