树上倍增
Eva.Q Lv9
2022-02-07 13:22:55

昨天，是明天的前天，是前天的明天。

树上倍增

今天和Co老师学了树上倍增

倍增思想

其实之前Co老师也给我讲过倍增思想，是在 ST Table 那一节。

倍增思想其实就是，每个数都可以转换成 二的幂次的和 。

为什么叫倍增呢？因为，

在树上，其就是对高度（深度）进行倍增思想。

例题

一

Eva.oj 0009

给一棵树，询问 点 的 级祖先是谁。

首先我们可以通过 dfs 求的每一个点的直接父亲是谁，根据倍增思想，我们可以求出每个点 级祖先是谁。 级祖先，可以通过不断找当前的二的幂次级的祖先，不断向上跳找到。

定义 f[i][j] 为 点 的 ​ 级祖先。

易错点：

数组要开够，但不要太大，因为二维数组的空间大小是乘法计算。

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
#include<bits/stdc++.h>
using namespace std;
#define N 500007
typedef long long ll;

vector<int> e[N];
int fa[N][21], n, p, rot;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

inline void dfs(int u) {
    for (int i = 1; i <= t; ++i)
            fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for (auto cur : e[u]) {
        int v = cur.first, w = cur.second;
        if (v != fa[u][0]) {
            fa[v][0] = u;
            dep[v] = dep[u] + 1;
            dfs(v);
        }
    }
}

int main() {
    n = rd(); q = rd(); rot = rd();
    for (int i = 1; i <= n - 1; ++i) {
        int u = rd(), v = rd();
        e[u].push_back(v); e[v].push_back(u);
    }
    fa[rot][0] = rot; dfs(rot);
    for (int i = 1; i <= 20; ++i)
        for (int j = 1; j <= n; ++j)
            fa[j][i] = fa[fa[j][i - 1]][i - 1];
    for (int i = 1; i <= q; ++i) {
        int u = rd(), k = rd();
        for (int j = 20; j >= 0; --j)
            if (k & (1 << i)) u = fa[u][i];
        printf("%d\n", u);
    }
    return 0;
}
二

洛谷

LCA 模板题 求最近公共祖先

首先，我们需要在 dfs 的过程中，求出每个点的深度，因为想用树上倍增解决这个问题，那就是对高度（深度）用倍增的思想解决问题，但两个点的深度有可能是不一样的，但从较浅的点到 ​ 这一段高度，两个人一定是相等的。所以我们把整个过程，分为两部分：

  1. 较深的点跳到和较浅的点一样的深度（也用倍增思想
  2. 两个点一起往上跳

假设做完步骤 以后从两个点到 的高度差为 ，可得若跳跃的高度差 ，两个点跳到的是同一个点，若跳跃的高度差 ，两个点跳到的不是同一个点，利用这个性质，我们将往上跳 ，故最后还需要 操作。

为什么是往上跳 呢，因为我们跳跃的条件是两个点往上跳的点不等，所以不可能停在 ，又因为根据倍增思想 一定能转化成二的幂次的和，所以我们一定会跳到这里。

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
#include<bits/stdc++.h>
using namespace std;
#define N 500007
typedef long long ll;

vector<int> e[N];
int fa[N][21], dep[N], t, n, m, rot;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

inline void dfs(int u) {
    for (int i = 1; i <= t; ++i)
            fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for (auto cur : e[u]) {
        int v = cur.first, w = cur.second;
        if (v != fa[u][0]) {
            fa[v][0] = u;
            dep[v] = dep[u] + 1;
            sum[v] = sum[u] + w;
            dfs(v);
        }
    }
}

inline int lca(int u, int v) {
    if (dep[u] > dep[v]) swap(u, v);
    for (int i = t; i >= 0; --i)
        if (dep[fa[v][i]] >= dep[u]) v = fa[v][i];
    if (u == v) return u;
    for (int i = t; i >= 0; --i)
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i]; v = fa[v][i];
        }
    return fa[u][0];
}

int main() {
    n = rd(); m = rd(); rot = rd();
    t = __lg(n - 1) + 1;
    for (int i = 1; i <= n - 1; ++i) {
        int u = rd(), v = rd();
        e[u].push_back(v); e[v].push_back(u);
    }
    fa[rot][0] = rot; dfs(rot);
    for (int i = 1; i <= m; ++i) {
        int u = rd(), v = rd();
        int ans = lca(u, v);
        printf("%d\n", ans);
    }
    return 0;
}

三

HDU ​​​ 树上两点距离

树上两个点的距离，可以转换为两个点到根节点的距离减去两倍他们的 到根节点的距离。

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
#include<bits/stdc++.h>
using namespace std;
#define N 500007
typedef long long ll;

vector<pair<int, int> > e[N];
int fa[N][21], dep[N], sum[N], t, n, m, rot;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

inline void dfs(int u) {
    for (int i = 1; i <= t; ++i)
            fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for (auto cur : e[u]) {
        int v = cur.first, w = cur.second;
        if (v != fa[u][0]) {
            fa[v][0] = u;
            dep[v] = dep[u] + 1;
            sum[v] = sum[u] + w;
            dfs(v);
        }
    }
}

inline int lca(int u, int v) {
    if (dep[u] > dep[v]) swap(u, v);
    for (int i = t; i >= 0; --i)
        if (dep[fa[v][i]] >= dep[u]) v = fa[v][i];
    if (u == v) return u;
    for (int i = t; i >= 0; --i)
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i]; v = fa[v][i];
        }
    return fa[u][0];
}

inline int getlen(int u, int v) {
    int ans = lca(u, v);
    return sum[u] + sum[v] - 2 * sum[ans];
}

inline void work(){
    n = rd(); m = rd();
    t = __lg(n - 1) + 1;
    for (int i = 1; i <= n - 1; ++i) {
        int u = rd(), v = rd(), w = rd();
        e[u].push_back(make_pair(v, w)); e[v].push_back(make_pair(u, w));
    }
    fa[1][0] = 1; dfs(1);
    for (int i = 1; i <= m; ++i) {
        int u = rd(), v = rd();
        printf("%d\n", getlen(u, v));
    }
}

int main() {
    int t = rd();
    while (t--) work();
    return 0;
}

四

HDU ​

不只一棵树。

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
#include<bits/stdc++.h>
using namespace std;
#define N 10007
typedef long long ll;

vector<pair<int, int> > e[N];
int fa[N][15], dep[N], sum[N], t, n, m, c;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

inline void dfs(int u) {
    for (int i = 1; i <= t; ++i)
            fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for (auto cur : e[u]) {
        int v = cur.first, w = cur.second;
        if (v != fa[u][0]) {
            fa[v][0] = u;
            dep[v] = dep[u] + 1;
            sum[v] = sum[u] + w;
            dfs(v);
        }
    }
}

inline int lca(int u, int v) {
    if (dep[u] > dep[v]) swap(u, v);
    for (int i = t; i >= 0; --i)
        if (dep[fa[v][i]] >= dep[u]) v = fa[v][i];
    if (u == v) return u;
    for (int i = t; i >= 0; --i)
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i]; v = fa[v][i];
        }
    if (fa[u][0] != fa[v][0]) return -1;
    return fa[u][0];
}

inline int getlen(int u, int v) {
    int ans = lca(u, v);
    if (ans == -1) return -1;
    return sum[u] + sum[v] - 2 * sum[ans];
}

inline void work(){
    for (int i = 1; i <= n; ++i) {e[i].clear(); sum[i] = dep[i] = fa[n][0] = 0;}
    t = __lg(n - 1) + 1;
    for (int i = 1; i <= m; ++i) {
        int u = rd(), v = rd(), w = rd();
        e[u].push_back(make_pair(v, w)); e[v].push_back(make_pair(u, w));
    }
    for (int i = 1; i <= n; ++i)
        if (dep[i] == 0) {
            fa[i][0] = i; dfs(i);
        }
    for (int i = 1; i <= c; ++i) {
        int u = rd(), v = rd();
        int ans = getlen(u, v);
        ans == -1 ? puts("Not connected") : printf("%d\n", ans);
    }
}

int main() {
    while (cin >> n >> m >> c) work();
    return 0;
}

五

树上前缀和/差分

洛谷

在一个树上，按 ​ 的顺序走，每路上每次经过的每个点都需要放一颗糖，问每个点各需要放多少颗糖。

本质就是对一个区间里面的数，都 +1。

树上前缀和，对于一条从点 到点 的路径，差分数组 d[u]++; d[v]++; d[lca(u, v)]--; d[fa[lca(u, v)][0]]--;

注意：fa[1][0] = 0;

因为对于从 开始以后的点，又是前一段的终点，又是后一段的起点，只用 +1，但我们重复计算，故需要再最后依次 -1。

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
#include<bits/stdc++.h>
using namespace std;
#define N 300007
typedef long long ll;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

vector<int> e[N];
int t, fa[N][20], dep[N], d[N], a[N];

inline void dfs(int x) {
    for (int i = 1; i <= t; ++i)
        fa[x][i] = fa[fa[x][i - 1]][i - 1];
    for (auto j : e[x]) {
        if(j != fa[x][0]) {
            fa[j][0] = x;
            dep[j] = dep[x] + 1;
            dfs(j);
        }
    }
}

inline int lca(int u, int v) {
    if (dep[u] > dep[v]) swap(u, v);
    for (int i = t; i >= 0; --i)
        if (dep[fa[v][i]] >= dep[u]) v = fa[v][i];
    if (u == v) return u;
    for (int i = t; i >= 0; --i)
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i]; v = fa[v][i];
        }
    if (fa[u][0] != fa[v][0]) return -1;
    return fa[u][0];
}

inline void dfs2(int x) {
    for (auto i : e[x])
        if (i != fa[x][0]) {
            dfs2(i);
            d[x] += d[i];
    }
}

int main() {
    int n = rd(); t = __lg(n - 1) + 1;
    for (int i = 1; i <= n; ++i) a[i] = rd();
    for (int i = 1; i <= n - 1; ++i) {
        int u = rd(), v = rd();
        e[u].push_back(v); e[v].push_back(u);
    }
    fa[1][0] = 0; dep[1] = 1; dfs(1);
    for (int i = 1; i < n; ++i) {
        int ans = lca(a[i], a[i + 1]);
        d[a[i]]++; d[a[i + 1]]++; d[ans]--; d[fa[ans][0]]--;
    }
    dfs2(1);
    for (int i = 2; i <= n; ++i) --d[a[i]];
    for (int i = 1; i <= n; ++i) printf("%d\n", d[i]);
    return 0;
}

六

判断树上两条路径是否有交点

洛谷

注意到树形结构不会出现环，所以如果有交必然有一个 Lca 在另一个 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
#include<bits/stdc++.h>
using namespace std;
#define N 100007
typedef long long ll;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

vector<int> V[N];
int t, fa[N][20], dep[N];

inline void dfs(int x) {
    for (int i = 1; i <= t; ++i)
        fa[x][i] = fa[fa[x][i - 1]][i - 1];
    for (auto j : V[x]) {
        if(j != fa[x][0]) {
            fa[j][0] = x;
            dep[j] = dep[x] + 1;
            dfs(j);
        }
    }
}

inline int lca(int u, int v) {
    if (dep[u] > dep[v]) swap(u, v);
    for (int i = t; i >= 0; --i)
        if (dep[fa[v][i]] >= dep[u]) v = fa[v][i];
    if (u == v) return u;
    for (int i = t; i >= 0; --i)
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i]; v = fa[v][i];
        }
    if (fa[u][0] != fa[v][0]) return -1;
    return fa[u][0];
}

inline int getlen(int u, int v) {
    int ans = lca(u, v);
    if (ans == -1) return -1;
    return dep[u] + dep[v] - 2 * dep[ans];
}

inline bool valid(int m, int l, int r) {
    return (lca(l, m) == m && dep[m] >= dep[r]);
}

inline bool check(int a, int b, int c, int d) {
    int l1 = lca(a, b), l2 = lca(c, d);
    return (valid(l2, a, l1) || valid(l2, b, l1) || valid(l1, c, l2) || valid(l1, d, l2));
}

int main() {
    int n = rd(), q = rd(); t = __lg(n - 1) + 1;
    for (int i = 1; i <= n - 1; ++i) {
        int u = rd(), v = rd();
        V[u].push_back(v); V[v].push_back(u);
    }
    for (int i = 1; i <= n; ++i)
        if (dep[i] == 0) {
            fa[i][0] = i; dfs(i);
        }
    for (int i = 1; i <= q; ++i) {
        int a = rd(), b = rd(), c = rd(), d = rd();
        puts(check(a, b, c, d) ? "Y" : "N");
    }
    return 0;
}
  • Post title：树上倍增
  • Post author：Eva.Q
  • Create time：2022-02-07 13:22:55
  • Post link：https://qyy/2022/02/07/Algorithm/multiply on the tree/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.