P3379 【模板】最近公共祖先（LCA）

题目描述

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

输入格式

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

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

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

输出格式

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

输入输出样例

输入 #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

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
const int INF=0x3f3f3f3f;
const int MAX=500000+10;
int n,m,s,x,y;
int anc[MAX][25],l[MAX];
bool vis[MAX];
struct edge{
	int to,next;
}e[MAX*2];
int head[MAX],tot=0;
void addedge(int u,int v){
	e[tot].to=v;
	e[tot].next=head[u];
	head[u]=tot++;
}
void dfs(int u){
	vis[u]=1;
	for(int i=head[u];i!=-1;i=e[i].next){
		int v = e[i].to;
		if(vis[v]) continue;
		l[v]=l[u]+1;
		anc[v][0]=u;
		fi(j,1,15) anc[v][j]=-1;//初始化为祖先不存在  这题卡常，log小点，或初始化一下
		dfs(v);
	}
}
void pre(){
	fi(j,1,21)
		fi(i,1,n+1)	
			if(anc[i][j-1]!=-1)
				anc[i][j]=anc[anc[i][j-1]][j-1]; //anc(i,j) 节点i的第2^j级祖先编号
} 
int lca(int p,int q){
	if(l[p]<l[q]) swap(p,q);
	for(int i=15;i>=0;i--)   //p q 同深度
		if(l[anc[p][i]]>=l[q])
			p=anc[p][i];
	if(p==q) return p;
	for(int i=15;i>=0;i--)
		if(anc[p][i]!=-1&&anc[p][i]!=anc[q][i]){
			p=anc[p][i];q=anc[q][i];   //向上
		}
	return anc[p][0];
}
int main(){
	freopen("in","r",stdin);
	mem(head,-1);
	sf(n);sf(m);sf(s);
	fi(i,0,n-1){
		sf(x);sf(y);
		addedge(x,y);
		addedge(y,x);
	}
	l[s]=1;anc[s][0]=-1;
	dfs(s);pre();
	while(m--){
		sf(x);sf(y);
		pf(lca(x,y));pfc("\n");
	}
	return 0;
}