满五的博客

Louis Aeilot's Blog

马上订阅 满五的博客 RSS 更新: https://blog.aeilot.top/index.xml

题解 最近公共祖先 (LCA)

2021年4月24日 17:45

好久没刷题了，复习一下：LCA。

题目详情

题目很简单，就是求多叉树两个点的最近公共祖先。

链接: 洛谷 P3379

LCA（Least Common Ancestors），即最近公共祖先，是指在有根树中，找出某两个结点u和v最近的公共祖先。 ———来自百度百科

818487-20151004150339121-181913844.png
图中，4 和 3 的 LCA 就是 1。

解题

最简单的方法 (暴力)

这种方法数据一大就会TLE。

原理很简单，让两个数一个一个向上走，直到两个数相遇。第一次相遇就是他们的 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
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
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

#define MAX 500000

vector<int> tree[MAX];// 以邻接表形式存储
int dep[MAX];
int fas[MAX];

namespace M1 {
    void dfs(int x, int fa) {
        if (fa != -1) {
            dep[x] = dep[fa] + 1;
        }...
剩余内容已隐藏
查看完整文章以阅读更多
查看完整文章