【-84】P3379 【模板】最近公共祖先(LCA)[tarjan]

题目描述

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

输入输出格式

输入格式:

第一行包含三个正整数N、M、S,分别表示树的结点个数、询问的个数和树根结点的序号。
接下来N-1行每行包含两个正整数x、y,表示x结点和y结点之间有一条直接连接的边(数据保证可以构成树)。
接下来M行每行包含两个正整数a、b,表示询问a结点和b结点的最近公共祖先。

输出格式:

输出包含M行,每行包含一个正整数,依次为每一个询问的结果。

输入输出样例

输入样例#1:

1
2
3
4
5
6
7
8
9
10
5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5

输出样例#1:

1
2
3
4
5
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。

题解

看了这篇博客,嗯看例子更好理解
伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Tarjan(u)//marge和find为并查集合并函数和查找函数
{
for each(u,v) //访问所有u子节点v
{
Tarjan(v); //继续往下遍历
marge(u,v); //合并v到u上
标记v被访问过;
}
for each(u,e) //访问所有和u有询问关系的e
{
如果e被访问过;
u,e的最近公共祖先为find(e);
}
}

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
)#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9')
{
k=k*10+(s-'0');
s=getchar();
}
return k*base;
}
int n,m,s,X,Y,d,ld;
int to[1000011];
int id[1000011];
int po[500011];//存图的
bool vis[500011];//标记是否访问过
int fa[500011];//祖先节点
int lto[1000011];
int lid[1000011];
int bj[1000011];
int lpo[500011];//存询问
int ans[500011];
//开始数组开小了各种MLE/TLE
inline int gf(int x)//并查集的找爸爸
{
if (fa[x]==x) return x;
fa[x]=gf(fa[x]);
return fa[x];
}
inline void un(int x,int y)//把y合到x里
{
x=gf(x);y=gf(y);
if (x!=y) fa[y]=x;
}
inline int dfs(int u)
{
vis[u]=1;
for (register int i=po[u];i;i=id[i])//扫u所连的边
{
if (!vis[to[i]])
{
dfs(to[i]);//先搜子节点
un(u,to[i]);//合并
}
}
for (register int i=lpo[u];i;i=lid[i])
{//看与点u有关的询问
if (vis[lto[i]])//如果扫过了那么他们的lca就是这个点所在的集合
{
ans[bj[i]]=gf(fa[lto[i]]);//存结果

}
}
}
int main()
{
n=read();m=read();s=read();
for (register int i=1;i<n;i++)
{//加边
fa[i]=i;
X=read();Y=read();
d++;
to[d]=Y;id[d]=po[X];po[X]=d;
d++;
to[d]=X;id[d]=po[Y];po[Y]=d;
}
fa[n]=n;
for (register int i=1;i<=m;i++)
{//询问
X=read();Y=read();
ld++;
bj[ld]=i;//标记所属询问编号
lto[ld]=Y;lid[ld]=lpo[X];lpo[X]=ld;
ld++;
bj[ld]=i;
lto[ld]=X;lid[ld]=lpo[Y];lpo[Y]=ld;
}
dfs(s);
for (int i=1;i<=m;i++) printf("%d\n",ans[i]);//输出
return 0;
}