LCA

发表于

题目

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

洛谷题目链接

读入格式

第一行包含三个正整数N、M、S，分别表示树的结点个数、询问的个数和树根结点的序号。

接下来N-1行每行包含两个正整数x、y，表示x结点和y结点之间有一条直接连接的边（数据保证可以构成树）。

接下来M行每行包含两个正整数a、b，表示询问a结点和b结点的最近公共祖先。

输出格式

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

输入样例一

5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5

输出样例一

4
4
1
4
4

题解

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
#include <stdio.h>
#include <iostream>
#define re register

//类模板快读 
template <class T> inline void read(T &x) {
	x=0;char c=getchar();
	for(; '0'>c || c>'9'; c=getchar());
	for(; '0'<=c && c<='9'; c=getchar()) x=(x<<1)+(x<<3)+(c^48);
}

//边数 
int cnt;

//双向建边，双倍空间，不做过多解释 
int To[1000005],Next[1000005],head[500005],d[500005];

//fa[u][i]为u往上跳2^i个点所到达的父亲 
int fa[500005][21];

//链式前向星 
inline void add(int u,int v) {
	To[++cnt]=v;
	Next[cnt]=head[u];
	head[u]=cnt;
}

//记录当前节点和父亲节点 
void dfs(int u,int Dad) {
	
	//当前深度=父亲+1； 
	d[u]=d[Dad]+1;
	
	//2^0=1,u往上跳1格所到达的父亲; 
	fa[u][0]=Dad;
	
	//fa[u][1]=fa[fa[u][0]][0]
	//以u为起点跳2格=自己的父亲跳一格
	//以此类推，感性理解 
	for(re int i=1; (1<<i)<=d[u]; ++i) fa[u][i]=fa[fa[u][i-1]][i-1];
	
	//遍历u节点为起始点的所有边 
	for(re int i=head[u]; i; i=Next[i])
	
	//因为之前是双向建边，所以为了防止来回跑，故进行判断 
		if(Dad^To[i]) dfs(To[i],u);
}

//重点！倍增LCA 
inline int LCA(int a,int b) {
	
	//确保a的深度小于b的深度
	if(d[a]>d[b]) std::swap(a,b);
	
	//接着要让它们跳到同一层,但一个一个慢慢往上跳太慢了，于是得定义它们的跳跃方式 
	//跳跃方式让我们抽象理解一下 
	//a是一个后面长眼睛的人 
	//最初i很大,跳的非常远，远到天边,深度底
	//而我们要做的是让a,b同层,跳到天边的,看不到,不予理会
	//i慢慢的小了,小到跳到a的后面了，能看到了，那就让b跳到这里
	//随着i慢慢缩小,b越来越小步的往前跳,慢慢缩进距离,直到同一层 
	 for(re int i=20; i>=0; --i) 
	 	if(d[a]<=d[fa[b][i]]) b=fa[b][i];
	
	//如果跳到同一层后数值相同，证明找到LCA了
	if(a==b) return a;
	
	//如果跳到同一层后数值仍不同，就一起往上跳，跳到fa[a][0]==fa[b][0]为止
	//跳跃方式与上文类似，只是不比较深度，而改为比较数值是否相同，也就是祖先是否一致
	//同一层开始一起跳，比较深度也没意义吧 
	for(re int i=20; i>=0; --i)
		if(fa[a][i] != fa[b][i]) 
			a=fa[a][i],b=fa[b][i];
	
	//找到啦!
	return fa[a][0]; 
}

int main() {
	int N,M,S;
	read(N),read(M),read(S);
	for(re int i=1,X,Y; i<N; ++i) {
		read(X),read(Y);
		
		//双向加边
		add(X,Y),add(Y,X);
	}
	dfs(S,0);
	for(re int i=1,A,B; i<=M; ++i) {
		read(A),read(B);
		
		//求二者的最近公共祖先 
		printf("%d\n",LCA(A,B));
	}
	return 0;
}