学习了 LCA(最近公共祖先) 这个高级的东西。。
于是乎来发一些理解和题解以便以后复习。

什么是LCA

LCA就是LCA
就是求一棵树上两个节点最近的公共祖先,那么有什么用呢,用来做题。

LCA的实现

这里用到了“爬树”的方法找
例如两个节点$x,y$:
规定$deepth_x>deepth_y$
1.让深的那个节点,$x$往树上爬,直到$deepth_x = deepth_y$;
2.让两个节点一起向上跳,如果碰在一起了,那么就找到了。
嗯,真是生动形象好理解呢!

代码实现

存储方式

一种神奇的存树、图的方式:
edge[cnt]数组存储了第cnt条边,其中to表示这条边指向的节点;pre则是指同一个点出发,比当前点早一个添加的边的编号,别的大佬好像是用nxt
head[x]存储了从x出发的所有边中最近添加的边
感受一下,会懂的😉

1
2
3
4
5
int head[MAXN];
struct Node
{
int to, pre;
}edge[(MAXN) * 2];

增加边

有了之上的存储方式,那么就有了下面的加边方法(cnt初始为0)

1
2
3
4
5
6
7
void addedge(int x, int y)
{
//edge[++cnt].to = y;
//edge[cnt].pre = head[x];
edge[++cnt] = (Node){head[x], y};//这句和上面两句一样,但它压行了
head[x] = cnt;
}

初始化

深搜初始化deepth数组(每个节点在树中的深度);
利用倍增思想,类似st表的方式,预处理father数组:
$father[x][i]$表示$x$节点向上爬$2^i$后的位置
更新方程式:
$father[now][i] = father[father[now][i - 1]][i - 1];$
解释:现在向上爬$2^i$的位置等于向上爬$2^{i-1}$再向上爬$2^{i-1}$

1
2
3
4
5
6
7
8
9
10
11
12
void build(int now, int fa)
{
father[now][0] = fa;
deepth[now] = deepth[fa] + 1;

for (int i = 1; (1 << i) <= deepth[now]; ++i)
father[now][i] = father[father[now][i - 1]][i - 1];

for (int i = head[now]; i; i = edge[i].pre)
if (edge[i].to != fa)//遍历下一条边,只要不是指向他父亲的就继续
build(edge[i].to, now);
}

查询

lca的关键部分,
看代码挺好理解的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int lca(int x, int y)
{
if (depth[x] < depth[y])//方便起见,规定x总比y深,不然换一下
swap(x, y);

for (int i = 29; i >= 0; --i)//让x向上爬,但不能比y浅,这里可以直接像我这样暴力30次,没有关系
if (depth[father[x][i]] >= depth[y])
x = father[x][i];

if (x == y) return x;//特判

for (int i = 29; i >= 0; --i)//xy一起向上跳
if (father[x][i] != father[y][i])
{
x = father[x][i];
y = father[y][i];
}
return father[x][0];//最后返回x节点上一层的节点,即为最近公共祖先
}

总的代码

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
#include <bits/stdc++.h>
#define MAXN 500000 + 9


using namespace std;

int cnt = 0, n, m, s;
int father[MAXN][30], head[MAXN], depth[MAXN];

struct Node
{
int to, pre;
}edge[(MAXN) * 2];

void addedge(int x, int y)
{
edge[++cnt].to = y;
edge[cnt].pre = head[x];
head[x] = cnt;
}

void dfs(int now, int fa)
{
father[now][0] = fa;
depth[now] = depth[fa] + 1;

for (int i = 1; (1 << i) <= depth[now]; ++i)
father[now][i] = father[father[now][i - 1]][i - 1];

for (int i = head[now]; i; i = edge[i].pre)
if (edge[i].to != fa)
dfs(edge[i].to, now);
}

int lca(int x, int y)
{
if (depth[x] < depth[y])
swap(x, y);

for (int i = 29; i >= 0; --i)
if (depth[father[x][i]] >= depth[y])
x = father[x][i];

if (x == y) return x;

for (int i = 29; i >= 0; --i)
if (father[x][i] != father[y][i])
{
x = father[x][i];
y = father[y][i];
}
return father[x][0];
}

int main()
{
int a, b;
scanf("%d%d%d", &n, &m, &s);
for (int i = 1; i <= n - 1; ++i)
{
scanf("%d%d", &a, &b);
addedge(a, b);
addedge(b, a);
}
dfs(s, 0);
for (int i = 1; i <= m; ++i)
{
scanf("%d%d", &a, &b);
printf("%d\n", lca(a, b));
}
return 0;
}

完事儿
peace~

评论