跳转至

树分治

例题

P3806 【模板】点分治 1 - 洛谷

多次查询是否存在距离为 \(k\) 的点对

代码
C++
 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
93
94
95
96
97
98
99
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
vector<array<int, 2>> adj[10005];
int son[10005], dp[10005];
bool vis[10005];
int rt, sumn;
void root(int u, int p) { // 求重心并设为根
    dp[u] = 0;
    son[u] = 1;
    for (auto &[to, w] : adj[u]) {
        if (to == p) continue;
        if (vis[to]) continue;
        root(to, u);
        son[u] += son[to];
        dp[u] = max(dp[u], son[to]);
    }
    dp[u] = max(dp[u], sumn - son[u]);
    if(dp[u] < dp[rt]) {
        rt = u;
    }
}
int dist[10005], rev[10005], tot;
bool flag[10000005];
int q[105], ans[105];
int st[10005];
int n, m;
void update(int u, int p) { // 更新子树信息
    if (dist[u] <= 10000000) { // 只需要到根节点距离<=10^7的点
        rev[++tot] = dist[u];
    }
    for (auto &[to, w] : adj[u]) {
        if (to == p) continue;
        if (vis[to]) continue;
        dist[to] = dist[u] + w;
        update(to, u);
    }
}
void work(int u) {
    int top = 0;
    for (auto &[to, w] : adj[u]) {
        if (vis[to]) continue;
        tot = 0;
        dist[to] = w;
        update(to, u);
        for (int i = 1 ; i <= tot ; i++) { // 遍历子树
            for (int j = 1 ; j <= m ; j++) { // 遍历所有查询
                if (q[j] >= rev[i]) {
                    ans[j] |= flag[q[j] - rev[i]];
                }
            }
        }
        for (int i = 1 ; i <= tot ; i++) { // 记录子树 to 的距离
            st[++top] = rev[i];
            flag[rev[i]] = true;
        }
    }
    for (int i = 1 ; i <= top ; i++) { // 清空当前所有操作
        flag[st[i]] = false;
    }
}
void divide(int u) {
    vis[u] = flag[0] = true;
    dist[u] = 0;
    work(u); // 对点 u 求解
    for (auto &[to, w] : adj[u]) {
        if (vis[to]) continue;
        sumn = son[to];
        dp[0] = n;
        rt = 0;
        root(to, u); // 查询子树 to 的重心
        divide(rt); // 点分治
    }
}
int main() {
    cin >> n >> m;
    for (int i = 1 ; i < n ; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    dp[0] = sumn = n;
    root(1, 0); // 初始化
    for (int i = 1 ; i <= m ; i++) {
        cin >> q[i];
    }
    divide(rt); // 点分治
    for (int i = 1 ; i <= m ; i++) {
        cout << (ans[i] ? "AYE" : "NAY") << "\n";
    }
    return 0;
}

P4178 Tree - 洛谷

求树上点对距离小于等于 \(k\) 的数量

代码
C++
 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
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
vector<array<int, 2>> adj[40005];
int son[40005], dp[40005];
bool vis[40005];
int rt, sumn;
void root(int u, int p) { // 求重心并设为根
    dp[u] = 0;
    son[u] = 1;
    for (auto &[to, w] : adj[u]) {
        if (to == p) continue;
        if (vis[to]) continue;
        root(to, u);
        son[u] += son[to];
        dp[u] = max(dp[u], son[to]);
    }
    dp[u] = max(dp[u], sumn - son[u]);
    if(dp[u] < dp[rt]) {
        rt = u;
    }
}
int dist[40005], rev[40005], tot;
int k, ans;
int n;
void update(int u, int p) {  // 更新子树信息
    if (dist[u] <= k) { // 只需要到根节点距离<=k的点
        rev[++tot] = dist[u];
    }
    for (auto &[to, w] : adj[u]) {
        if (to == p) continue;
        if (vis[to]) continue;
        dist[to] = dist[u] + w;
        update(to, u);
    }
}
int work(int u, int w) {
    tot = 0;
    update(u, 0); // 更新距离
    sort(rev + 1, rev + tot + 1); // 排序双指针求解
    int L = 1, R = tot, res = 0;
    while (L <= R) {
        if (rev[L] + rev[R] <= k) {
            res += R - L;
            L++;
        } else {
            R--;
        }
    }
    return res;
}
void divide(int u) {
    vis[u] = true;
    dist[u] = 0;
    ans += work(u, 0); // 计算点 u 的答案
    for (auto &[to, w] : adj[u]) {
        if (vis[to]) continue;
        dist[to] = w;
        ans -= work(to, w); // 对点 to 容斥, 删去重复计算的点
        sumn = son[to];
        dp[0] = n;
        rt = 0;
        root(to, u); // 查询子树 to 的重心
        divide(rt); // 点分治
    }
}
int main() {
    cin >> n;
    for (int i = 1 ; i < n ; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    dp[0] = sumn = n;
    root(1, 0); // 初始化
    cin >> k;
    divide(rt); // 点分治
    cout << ans << "\n";
    return 0;
}

求树上点对距离为 \(3\) 的倍数的数量

P2634 [国家集训队] 聪聪可可 - 洛谷

代码
C++
 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
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
vector<array<int, 2>> adj[40005];
int son[40005], dp[40005];
bool vis[40005];
int rt, sumn;
void root(int u, int p) { // 求重心并设为根
    dp[u] = 0;
    son[u] = 1;
    for (auto &[to, w] : adj[u]) {
        if (to == p) continue;
        if (vis[to]) continue;
        root(to, u);
        son[u] += son[to];
        dp[u] = max(dp[u], son[to]);
    }
    dp[u] = max(dp[u], sumn - son[u]);
    if(dp[u] < dp[rt]) {
        rt = u;
    }
}
int dist[40005], s[3], tot;
int ans;
int n;
void update(int u, int p) {  // 更新子树信息
    s[dist[u] % 3]++;
    for (auto &[to, w] : adj[u]) {
        if (to == p) continue;
        if (vis[to]) continue;
        dist[to] = dist[u] + w;
        update(to, u);
    }
}
int work(int u) {
    tot = 0;
    s[0] = s[1] = s[2] = 0;
    update(u, 0); // 更新距离
    return s[2] * s[1] * 2 + s[0] * s[0];
}
void divide(int u) {
    vis[u] = true;
    dist[u] = 0;
    ans += work(u); // 计算点 u 的答案
    for (auto &[to, w] : adj[u]) {
        if (vis[to]) continue;
        dist[to] = w;
        ans -= work(to); // 对点 to 容斥, 删去重复计算的点
        sumn = son[to];
        dp[0] = n;
        rt = 0;
        root(to, u); // 查询子树 to 的重心
        divide(rt); // 点分治
    }
}
int main() {
    cin >> n;
    for (int i = 1 ; i < n ; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    dp[0] = sumn = n;
    root(1, 0); // 初始化
    divide(rt); // 点分治
    int fm = n * n;
    int k = __gcd(ans, fm);
    ans /= k;
    fm /= k;
    cout << ans << "/" << fm << "\n";
    return 0;
}

P5306 [COCI2018-2019#5] Transport - 洛谷

\(n\) 个城市, \(n-1\) 条路, 每条路都有消耗 \(w\) 单位油, 每个城市都可以加 \(v\) 单位油.

问有多少有序对 \((u,v)\) 满足, 起始油量为 \(0\) 的车, 可以从 \(u\) 出发, 抵达 \(v\).

点分治

当以 \(rt\) 为根时, \(w_i\) 表示 \(rt\) 到 \(i\) 的点权和, \(d_i\) 表示 \(rt\) 到 \(i\) 的边权和

①从 \(i\) 到 \(rt\), 对路径上任意点 \(j\) 都有 \(w_i-w_j\ge d_i-d_j\).

可以把式子化为 \(w_i-d_i-(w_j-d_j)\ge0\) 等价于 \(w_i-d_i-\max(w_j-d_j)\ge0\)

那么我们只需要子树中最大的 \(w_j-d_j\) 即可.

②从 \(rt\) 到 \(i\), 此时起点不一定是 \(rt\), 可以是其他子树的一个点 \(k\), 设从 \(k\) 到 \(rt\) 剩余 \(x\) 单位油, 则 对路径上任意点 \(j\) 都有 \(x+w_{fa_j}\ge d_j\), 变换一下得 \(x+w_{fa_j}-d_j\ge0\), 那么我们只需要子树中的最小的 \(w_{fa_j}-d_j\) 即可.

代码
C++
  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
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
vector<array<int, 2>> adj[100005];
int son[100005], dp[100005];
bool vis[100005];
int rt, sumn;
void root(int u, int p) { // 求重心并设为根
    dp[u] = 0;
    son[u] = 1;
    for (auto &[to, w] : adj[u]) {
        if (to == p) continue;
        if (vis[to]) continue;
        root(to, u);
        son[u] += son[to];
        dp[u] = max(dp[u], son[to]);
    }
    dp[u] = max(dp[u], sumn - son[u]);
    if(dp[u] < dp[rt]) {
        rt = u;
    }
}
i64 d[100005], w[100005];
i64 st1[100005], tot1, st2[100005], tot2;
int n;
int a[100005];
void update(int u, int p, i64 mx, i64 mi) { // 更新子树信息
    if (w[u] - d[u] >= mx) { // 合法才记录
        st1[++tot1] = w[u] - d[u];
    }
    st2[++tot2] = mi;
    for (auto &[to, z] : adj[u]) {
        if (to == p) continue;
        if (vis[to]) continue;
        d[to] = d[u] + z;
        w[to] = w[u] + a[to];
        update(to, u, max(mx, w[u] - d[u]), min(mi, w[u] - d[to]));
    }
}
i64 st3[100005], tot3, st4[100005], tot4;
i64 ans = 0;
void work(int u) {
    tot3 = tot4 = 0;
    d[u] = 0;
    w[u] = a[u];
    for (auto &[to, z] : adj[u]) {
        if (vis[to]) continue;
        tot1 = tot2 = 0;
        d[to] = z;
        w[to] = w[u] + a[to];
        update(to, u, w[u] - d[u], w[u] - d[to]);
        sort(st1 + 1, st1 + tot1 + 1);
        sort(st2 + 1, st2 + tot2 + 1);
        int L = 1;
        for (int i = tot2 ; i >= 1 ; i--) {
            while (L <= tot1 && st1[L] + st2[i] - a[u] < 0) {
                L++;
            }
            ans -= tot1 - L + 1;
        }
        for (int i = 1 ; i <= tot1 ; i++) {
            st3[++tot3] = st1[i];
        }
        for (int i = 1 ; i <= tot2 ; i++) {
            st4[++tot4] = st2[i];
        }
    }
    sort(st3 + 1, st3 + tot3 + 1);
    sort(st4 + 1, st4 + tot4 + 1);
    int L = 1;
    for (int i = tot4 ; i >= 1 ; i--) {
        if (st4[i] >= 0) {
            ans++;
        }
        while (L <= tot3 && st3[L] + st4[i] - a[u] < 0) {
            L++;
        }
        ans += tot3 - L + 1;
    }
    ans += tot3;
}
void divide(int u) {
    vis[u] = true;
    work(u); // 对点 u 求解
    for (auto &[to, w] : adj[u]) {
        if (vis[to]) continue;
        sumn = son[to];
        dp[0] = n;
        rt = 0;
        root(to, u); // 查询子树 to 的重心
        divide(rt); // 点分治
    }
}
int main() {
    cin >> n;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
    }
    for (int i = 1 ; i < n ; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    dp[0] = sumn = n;
    root(1, 0); // 初始化
    divide(rt); // 点分治
    cout << ans << "\n";
    return 0;
}

P3060 [USACO12NOV] Balanced Trees G - 洛谷

\(n\) 个点的树, 每个点有左括号或右括号, 在一条简单路径的括号能匹配的情况下, 最大嵌套层数是多少?

考虑从 \(i\) 到 \(rt\), 有两种, 此时记左括号权值为 \(1\), 右括号权值为 \(-1\)

①以左括号开头, 符合条件的一定要每个前缀都 \(ge0\), 我们需要维护这个前缀的最小值 \(Lmi\), 每次取 \(\min(Lmi+a_{to},0)\) 即可. 为了计算答案我们需要左括号的最长前缀 \(Lmx\) 和左括号多的数量 \(Ldis\).

②以右括号开头, 我们将前缀的值取反, 符合条件的一定要每个前缀都 \(ge0\), 我们需要维护这个前缀的最小值 \(Rmi\), 每次取 \(\min(Rmi-a_{to},0)\) 即可. 为了计算答案我们需要左括号的最长前缀 \(Rmx\) 和右括号多的数量 \(Rdis\).

考虑计算答案, 一定是 \(Ldis=Rdis\) 的情况下 \(\max(Lmx,Ldis+Rmx)\)

代码
C++
  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
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
            #include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
vector<int> adj[40005];
int son[40005], dp[40005];
bool vis[40005];
int rt, sumn;
void root(int u, int p) { // 求重心并设为根
    dp[u] = 0;
    son[u] = 1;
    for (auto &to : adj[u]) {
        if (to == p) continue;
        if (vis[to]) continue;
        root(to, u);
        son[u] += son[to];
        dp[u] = max(dp[u], son[to]);
    }
    dp[u] = max(dp[u], sumn - son[u]);
    if(dp[u] < dp[rt]) {
        rt = u;
    }
}
int n;
int a[40005];
array<int, 2> st1[40005], st2[40005];
int tot1, tot2;
array<int, 2> flag[40005];
void update(int u, int p, int Ldis, int Rdis, int Lmx, int Rmx, int Lmi, int Rmi) { // 更新子树信息
    // Ldis 为左链 左括号多的数量
    // Rdis 为右链 右括号多的数量
    // Lmx 为左链 左括号最长前缀
    // Rmx 为右链 左括号最长前缀
    // Lmi 为左链 左括号最小前缀
    // Rmi 为左链 右括号最小前缀
    if (Lmi >= 0) {
        st1[++tot1] = {Ldis, Lmx};
    }
    if (Rmi >= 0) {
        st2[++tot2] = {Rdis, Rmx};
    }
    for (auto &to : adj[u]) {
        if (to == p) continue;
        if (vis[to]) continue;
        update(to, u, Ldis + a[to], Rdis - a[to], max(Lmx + a[to], a[to]), max(Rmx, -Rdis + a[to]), min(Lmi + a[to], 0), min(Rmi - a[to], 0));
    }
}
int ans = 0;
void work(int u) {
    tot1 = tot2 = 0;
    for (auto &to : adj[u]) {
        if (vis[to]) continue;
        int last1 = tot1, last2 = tot2;
        update(to, u, a[to], -(a[u] + a[to]), a[to], max({0, a[u], a[u] + a[to]}), min(a[to], 0), min(-(a[u] + a[to]), 0));
        for (int i = last2 + 1 ; i <= tot2 ; i++) {
            if (flag[st2[i][0]][0]) {
                // flag[st2[i][0]][1] 为  左链最长前缀
                // st2[i][0] 为 左链的和
                // st2[i][1] 为 左链最长前缀
                ans = max({ans, flag[st2[i][0]][1], st2[i][0] + st2[i][1]});
            }
        }
        for (int i = last1 + 1 ; i <= tot1 ; i++) {
            flag[st1[i][0]][0] = 1;
            flag[st1[i][0]][1] = max(flag[st1[i][0]][1], st1[i][1]);
        }
    }
    if (a[u] == -1) {
        ans = max(ans, flag[1][1]);
    } else {
        for (int i = 1 ; i <= tot2 ; i++) {
            if (st2[i][0] == 0) {
                ans = max(ans, st2[i][1]);
            }
        }
    }
    for (int i = 1 ; i <= tot1 ; i++) {
        flag[st1[i][0]] = {0, 0};
    }
    tot1 = tot2 = 0;
    for (int _ = (int) adj[u].size() - 1 ; _ >= 0 ; _--) {
        int to = adj[u][_];
        if (vis[to]) continue;
        int last1 = tot1, last2 = tot2;
        update(to, u, a[to], -(a[u] + a[to]), a[to], max({0, a[u], a[u] + a[to]}), min(a[to], 0), min(-(a[u] + a[to]), 0));
        for (int i = last2 + 1 ; i <= tot2 ; i++) {
            if (flag[st2[i][0]][0]) {
                ans = max({ans, flag[st2[i][0]][1], st2[i][0] + st2[i][1]});
            }
        }
        for (int i = last1 + 1 ; i <= tot1 ; i++) {
            flag[st1[i][0]][0] = 1;
            flag[st1[i][0]][1] = max(flag[st1[i][0]][1], st1[i][1]);
        }
    }
    if (a[u] == -1) {
        ans = max(ans, flag[1][1]);
    } else {
        for (int i = 1 ; i <= tot2 ; i++) {
            if (st2[i][0] == 0) {
                ans = max(ans, st2[i][1]);
            }
        }
    }
    for (int i = 1 ; i <= tot1 ; i++) {
        flag[st1[i][0]] = {0, 0};
    }
}
void divide(int u) {
    vis[u] = true;
    work(u); // 对点 u 求解
    for (auto &to : adj[u]) {
        if (vis[to]) continue;
        sumn = son[to];
        dp[0] = n;
        rt = 0;
        root(to, u); // 查询子树 to 的重心
        divide(rt); // 点分治
    }
}
int main() {
    cin >> n;
    for (int i = 2 ; i <= n ; i++) {
        int p;
        cin >> p;
        adj[p].push_back(i);
        adj[i].push_back(p);
    }
    for (int i = 1 ; i <= n ; i++) {
        char ch;
        cin >> ch;
        if (ch == '(') {
            a[i] = 1;
        } else {
            a[i] = -1;
        }
    }
    dp[0] = sumn = n;
    root(1, 0); // 初始化
    divide(rt); // 点分治
    cout << ans << "\n";
    return 0;
}