竞赛算法(6) 树上问题

树的dfs#

完美, 简洁, 易于理解. 以维护子树大小为例:

1
int siz[N];
2
vector<int> adj[N]; // 邻接表存无向边
3

4
auto dfs = [&](auto&& self, int x, int p) {
5
    siz[x] = 1;
6
    for (const auto& y : adj[x]) {
7
        if (y == p) continue;
8
        self(self, y, x);
9
        siz[x] += siz[y];
10
    }
11
};
12

13
// 调用
14
dfs(dfs, root, -1);

LCA#

倍增算法#

在 $O(N\log N)$ 的时间内预处理, 在 $O(\log N)$ 时间内查询.

1
constexpr int N = 2e5 + 50;
2
constexpr int LOG = 20; // 2^18 约 26 万
3
int up[N][LOG + 1];
4
int depth[N];
5
vector<int> adj[N];
6

7
// 预处理depth数组和up数组
8
void dfs(int x, int p) {
9
    for (int i = 1; i <= LOG; i++) {
10
        up[x][i] = up[up[x][i - 1]][i - 1];
11
    }
12
    for (const auto& y : adj[x]) {
13
        if (y == p) continue;
14
        depth[y] = depth[x] + 1;
15
        up[y][0] = x;
16
        dfs(y, x);
17
    }
18
}
19

20
// 求lca
21
int getlca(int x, int y) {
22
    if (depth[x] < depth[y]) swap(x, y);
23

24
    for (int i = LOG; i >= 0; i--) {
25
        if (depth[x] - (1 << i) >= depth[y]) {
26
            x = up[x][i];
27
        }
28
    }
29

30
    if (x == y) {
31
        return x;
32
    }
33

34
    for (int i = LOG; i >= 0; i--) {
35
        if (up[x][i] != up[y][i]) {
36
            x = up[x][i];
37
            y = up[y][i];
38
        }
39
    }
40
    return up[x][0];
41
}

基于LCA求树上两点距离#

1
int dist(int x, int y) {
2
    return depth[x] + depth[y] - 2 * depth[getlca(x, y)];
3
}