最近公共祖先(LCA)
LCA最近公共祖先解决的是：对于有根树T的两个结点u、v，最近公共祖先LCA(T,u,v)表示一个结点x，满足x是u、v的祖先且x的深度尽可能大。
通俗地讲就是下面的这个例子：
在上图中10和12的LCA就是3。
核心思路
模拟法
根据题意进行模拟。一步一步回向根节点递进，分别对到达的顶点标号，碰到的第一个两个都到达过的顶点即为两点的LCA了。
这样的做法非常自然，但是绝对不可能符合这一道题所要求的时间复杂度。
倍增法
仍旧是按照题意进行模拟，不同的是，这次不再一次一次向上找，这次以2的倍数从上向下找。
具体的操作步骤很简单，首先将两节点调到保证deep[X]>=deep[Y]，如果这个时候两点是同一点则可以直接出答案，如果不行则将X从上向下跳。为什么要从上往下跳呢？
通过上面的这个例子可以看出，如果从下向上的话，有可能跳到的那一个点不是最近公共祖先，而从上向下可以在找到后继续向下。
代码分解
p[i][j] 表示节点i的2j级祖先。
dfs求深度
1
2
3
4
5
6
7
8
9
10
11
| void dfs(int u,int fa) {
d[u]=d[fa]+1;
p[u][0]=fa;
for(int i=1; (1<<i)<=d[u]; i++)
p[u][i]=p[p[u][i-1]][i-1];
for(int i=head[u];i;i=next[i]) {
int v=to[i];
if(v!=fa)
dfs(v,u);
}
}
|
上述的状态转移的含义是：
u的2i个祖先和u的2i−1个祖先的2i−1是同一个祖先
数学逻辑来讲就是2i=2×2×…×2×2(共有i个2)
而2i−1=2×2×…×2×2(共有i-1个2)
根据乘法分配律，得出2i−1+2i−1=2i并且要满足2i≤d[u]，其d[u]是该节点的深度。
所以上面的含义也就成立，可以得出每一个节点的任意的祖先（这里没有边权的概念）。
ST求LCA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| int lca(int a,int b) {
if(d[a]>d[b]) swap(a,b);
for(int i=20; i>=0; i--)
if(d[a]<=d[b]-(1<<i))
b=p[b][i];
if(a==b) return a;
for(int i=20; i>=0; i--) {
if(p[a][i]==p[b][i]) continue;
else {
a=p[a][i];
b=p[b][i];
}
}
return p[a][0];
}
|
这一步的操作也比较简单。首先必须确保a的深度要小于或等于b的深度。然后将深度大的b由上向下跳，可以说是从220开始逐步向下（这样可以有效降低代码难度而对程序运行几乎没有影响）。直到b刚刚跳到了a的上面。此时a与b的LCA就一定在a和b之间了。接下来的操作与刚才的非常相似，同样是进行20次“徘徊”，详细的内容见上方注释。
完整代码
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
| #include<bits/stdc++.h>
#define MAXN 500000+10
using namespace std;
int head[MAXN<<1],to[MAXN<<1],next[MAXN<<1],cnt=0;
int n,m,s;
void addedge(int u,int v) {
cnt++;
to[cnt]=v;
next[cnt]=head[u];
head[u]=cnt;
}
int read() {
}
int d[MAXN],p[MAXN][21];
void dfs(int u,int fa) {
d[u]=d[fa]+1;
p[u][0]=fa;
for(int i=1; (1<<i)<=d[u]; i++)
p[u][i]=p[p[u][i-1]][i-1];
for(int i=head[u];i;i=next[i]) {
int v=to[i];
if(v!=fa)
dfs(v,u);
}
}
int lca(int a,int b) {
if(d[a]>d[b]) swap(a,b);
for(int i=20; i>=0; i--)
if(d[a]<=d[b]-(1<<i))
b=p[b][i];
if(a==b) return a;
for(int i=20; i>=0; i--) {
if(p[a][i]==p[b][i]) continue;
else {
a=p[a][i];
b=p[b][i];
}
}
return p[a][0];
}
int main() {
memset(head,-1,sizeof(head));
n=read(); m=read(); s=read();
for(int i=1; i<=n-1; i++) {
int x,y;
x=read(),y=read();
addedge(x,y);
addedge(y,x);
}
dfs(s,0);
for(int i=1; i<=m; i++) {
int a=read(),b=read();
printf("%d\n",lca(a,b));
}
return 0;
}
|
