收费标准评估

GitHub跳转原题关系图 Canvas 关系图返回列表

用 Link-Cut Tree 的路径矩阵维护动态树形 DP，同时维护虚子树贡献以支持换根和子树查询。

OJ: shumeng

题目 ID: CSP202503E

难度:提高+/省选-

标签:Link-Cut Tree动态树树形 DP

日期: 2026-07-31 16:21

形式化题目

一棵树，每个节点有权值 $a_i$ （可为负）。以某点为根时，定义"基本费用"为所有包含根节点的连通子图中权值和的最大值。维护四种操作：查询某子树内的最优连通子图、修改点权、换根、断边重连，并在每次操作后输出当前基本费用。

思路

核心是动态树上的树形 DP。先看每次重建树的朴素做法：

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:52
 */
// brute.cpp：每次重建根树并做树形 DP，适合小数据验证。
#include <bits/stdc++.h>
using namespace std;

int n;
vector<vector<int> > graph;
vector<long long> weight_value;
vector<long long> down_value;
vector<long long> best_value;

void dfs(int u, int parent) {
    down_value[u] = weight_value[u];
    best_value[u] = LLONG_MIN / 4;
    for (int i = 0; i < (int)graph[u].size(); i++) {
        int v = graph[u][i];
        if (v == parent) {
            continue;
        }
        dfs(v, u);
        down_value[u] += max(0LL, down_value[v]);
        best_value[u] = max(best_value[u], best_value[v]);
    }
    best_value[u] = max(best_value[u], down_value[u]);
}

long long root_answer(int root) {
    dfs(root, 0);
    return down_value[root];
}

long long subtree_answer(int root, int target) {
    dfs(root, 0);
    return best_value[target];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m;
    cin >> n >> m;
    graph.assign(n + 1, vector<int>());
    weight_value.assign(n + 1, 0);
    down_value.assign(n + 1, 0);
    best_value.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> weight_value[i];
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    int current_root = 1;
    cout << root_answer(current_root) << '\n';
    while (m--) {
        int type;
        cin >> type;
        if (type == 1) {
            int u;
            cin >> u;
            cout << subtree_answer(current_root, u) << '\n';
        } else if (type == 2) {
            int u;
            long long x;
            cin >> u >> x;
            weight_value[u] = x;
            cout << root_answer(current_root) << '\n';
        } else if (type == 3) {
            cin >> current_root;
            cout << root_answer(current_root) << '\n';
        } else {
            int a, b, c, d;
            cin >> a >> b >> c >> d;
            for (int i = 0; i < (int)graph[a].size(); i++) {
                if (graph[a][i] == b) {
                    graph[a].erase(graph[a].begin() + i);
                    break;
                }
            }
            for (int i = 0; i < (int)graph[b].size(); i++) {
                if (graph[b][i] == a) {
                    graph[b].erase(graph[b].begin() + i);
                    break;
                }
            }
            graph[c].push_back(d);
            graph[d].push_back(c);
            cout << root_answer(current_root) << '\n';
        }
    }
    return 0;
}

树形 DP 的两个量

对每个节点 $u$ 定义：

$F_u$ ：必须包含 $u$ 的连通子图的最大权和；
$G_u$ ： $u$ 所在子树内任意连通子图的最大权和。

有转移：

F_u = a_u + \sum_{v \in child(u)} \max(0, F_v), \qquad G_u = \max(F_u, \max_{v \in child(u)} G_v)

由于允许选择负权节点（即使收益为负也要选，因为必须连通）， $\max(0, F_v)$ 表示"接不接这个孩子的子树"。

把转移写成矩阵

在一条首选路径（实链）上，下方子链的状态 $(F,G)$ 经过当前节点 $u$ 后的变换为：

F'=\max(a_u + F, a_u), \qquad G'=\max(a_u + F, G, a_u, b_u)

其中 $a_u$ 是节点权值加上虚子树 $\max(0,F)$ 之和， $b_u$ 是虚子树 $G$ 的最大值。这是一个 max-plus 矩阵变换，可以用 $3\times 3$ 矩阵表示，Link-Cut Tree 的 Splay 节点维护路径上矩阵的复合。

虚子树用 multiset 维护

access 操作会让实链和虚子树互相转换。对每个节点用两个 multiset 分别保存虚子树的 $\max(0,F)$ 总和与 $G$ 最大值，从而支持 $O(\log n)$ 的插入删除。于是：

基本费用 = 根节点的 $F$ 值；
换根后 access(u)， $u$ 的虚子树贡献直接给出其子树内 $G$ ；
改权、断边、连边都是 Link-Cut Tree 的标准操作。

代码

cpp

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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:52
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000;
const long long NEG = -(1LL << 60) * 4;

struct Matrix {
    long long a[3][3]; // max-plus 矩阵，用于路径上状态 (F,G) 的复合变换
};

int n, m;
long long value_weight[MAXN + 1]; // 每个景点的收费，可能为负
int fa[MAXN + 1];                 // Splay 树父亲
int son[MAXN + 1][2];             // Splay 树左右孩子
bool reversed_tag[MAXN + 1];      // 翻转懒标记
Matrix forward_matrix[MAXN + 1];  // 正方向复合矩阵（链头->链尾）
Matrix backward_matrix[MAXN + 1]; // 反方向复合矩阵（链尾->链头）
Matrix node_matrix[MAXN + 1];     // 单个节点的变换矩阵

long long virtual_sum[MAXN + 1];  // 虚子树 max(0,F) 之和
long long virtual_best[MAXN + 1]; // 虚子树 G 的最大值
multiset<pair<long long, int> > virtual_f[MAXN + 1]; // 虚子树按 (F, 节点) 排序，便于删除
multiset<pair<long long, int> > virtual_g[MAXN + 1]; // 虚子树按 (G, 节点) 排序，便于删除
long long saved_f[MAXN + 1];      // 记录虚子树接入时的 F 值
long long saved_g[MAXN + 1];      // 记录虚子树接入时的 G 值

// 单位矩阵：对角线为 0，其余为负无穷
Matrix identity_matrix() {
    Matrix result;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            result.a[i][j] = (i == j) ? 0 : NEG;
        }
    }
    return result;
}

// max-plus 矩阵乘法：C[i][j] = max_k(A[i][k] + B[k][j])
Matrix compose(const Matrix &left, const Matrix &right) {
    Matrix result;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            result.a[i][j] = NEG;
            for (int k = 0; k < 3; k++) {
                if (left.a[i][k] <= NEG / 2 || right.a[k][j] <= NEG / 2) {
                    continue;
                }
                result.a[i][j] = max(result.a[i][j],
                                     left.a[i][k] + right.a[k][j]);
            }
        }
    }
    return result;
}

Matrix get_forward(int u) {
    if (u == 0) {
        return identity_matrix();
    }
    return forward_matrix[u];
}

Matrix get_backward(int u) {
    if (u == 0) {
        return identity_matrix();
    }
    return backward_matrix[u];
}

// 根据当前节点(含其虚子树)重新计算节点矩阵。
// a = 本节点收费 + 虚子树 max(0,F) 之和；b = 虚子树 G 的最大值。
void update_node_matrix(int u) {
    long long a = value_weight[u] + virtual_sum[u];
    long long b = virtual_best[u];
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            node_matrix[u].a[i][j] = NEG;
        }
    }
    // F' = max(a + F, a), G' = max(a + F, G, a, b).
    node_matrix[u].a[0][0] = a;
    node_matrix[u].a[0][2] = a;
    node_matrix[u].a[1][0] = a;
    node_matrix[u].a[1][1] = 0;
    node_matrix[u].a[1][2] = max(a, b);
    node_matrix[u].a[2][2] = 0;
}

// 更新 u 的正向/反向矩阵：左儿子矩阵 * 本节点矩阵 * 右儿子矩阵
void pull(int u) {
    update_node_matrix(u);
    Matrix left_forward = get_forward(son[u][0]);
    Matrix right_forward = get_forward(son[u][1]);
    Matrix middle = compose(left_forward, node_matrix[u]);
    forward_matrix[u] = compose(middle, right_forward);

    Matrix right_backward = get_backward(son[u][1]);
    Matrix left_backward = get_backward(son[u][0]);
    middle = compose(right_backward, node_matrix[u]);
    backward_matrix[u] = compose(middle, left_backward);
}

// 给 u 打上区间翻转标记：交换左右儿子，并交换正反矩阵
void apply_reverse(int u) {
    if (u == 0) {
        return;
    }
    swap(son[u][0], son[u][1]);
    swap(forward_matrix[u], backward_matrix[u]);
    reversed_tag[u] = !reversed_tag[u];
}

void push_down(int u) {
    if (!reversed_tag[u]) {
        return;
    }
    apply_reverse(son[u][0]);
    apply_reverse(son[u][1]);
    reversed_tag[u] = false;
}

bool is_splay_root(int u) {
    return son[fa[u]][0] != u && son[fa[u]][1] != u;
}

void rotate(int u) {
    int y = fa[u];
    int z = fa[y];
    int direction = (son[y][1] == u);
    int middle = son[u][direction ^ 1];
    if (!is_splay_root(y)) {
        son[z][son[z][1] == y] = u;
    }
    fa[u] = z;
    son[u][direction ^ 1] = y;
    fa[y] = u;
    son[y][direction] = middle;
    if (middle != 0) {
        fa[middle] = y;
    }
    pull(y);
    pull(u);
}

void splay(int u) {
    static int stack_nodes[MAXN + 1];
    int top = 0;
    int x = u;
    stack_nodes[++top] = x;
    while (!is_splay_root(x)) {
        x = fa[x];
        stack_nodes[++top] = x;
    }
    while (top > 0) {
        push_down(stack_nodes[top--]);
    }
    while (!is_splay_root(u)) {
        int y = fa[u];
        int z = fa[y];
        if (!is_splay_root(y)) {
            if ((son[y][0] == u) == (son[z][0] == y)) {
                rotate(y);
            } else {
                rotate(u);
            }
        }
        rotate(u);
    }
    pull(u);
}

int leftmost(int u) {
    int x = u;
    while (true) {
        push_down(x);
        if (son[x][0] == 0) {
            return x;
        }
        x = son[x][0];
    }
}

long long evaluate_f(int u) {
    if (u == 0) {
        return NEG;
    }
    return forward_matrix[u].a[0][2];
}

long long evaluate_g(int u) {
    if (u == 0) {
        return NEG;
    }
    return forward_matrix[u].a[1][2];
}

// access 时把一条实链换成虚子树：向父节点登记/撤销它的 F 与 G 贡献
void add_virtual(int parent, int path_root) {
    if (path_root == 0) {
        return;
    }
    int child = leftmost(path_root);
    long long f = max(0LL, evaluate_f(path_root));
    long long g = evaluate_g(path_root);
    saved_f[child] = f;
    saved_g[child] = g;
    virtual_f[parent].insert(make_pair(f, child));
    virtual_g[parent].insert(make_pair(g, child));
    virtual_sum[parent] += f;
    virtual_best[parent] = max(virtual_best[parent], g);
}

// 从父节点的虚子树集合中删除某个实链根对应的贡献
void remove_virtual(int parent, int path_root) {
    if (path_root == 0) {
        return;
    }
    int child = leftmost(path_root);
    long long f = saved_f[child];
    long long g = saved_g[child];
    multiset<pair<long long, int> >::iterator it_f;
    multiset<pair<long long, int> >::iterator it_g;
    it_f = virtual_f[parent].find(make_pair(f, child));
    it_g = virtual_g[parent].find(make_pair(g, child));
    if (it_f != virtual_f[parent].end()) {
        virtual_f[parent].erase(it_f);
    }
    if (it_g != virtual_g[parent].end()) {
        virtual_g[parent].erase(it_g);
    }
    virtual_sum[parent] -= f;
    if (virtual_g[parent].empty()) {
        virtual_best[parent] = NEG;
    } else {
        virtual_best[parent] = virtual_g[parent].rbegin()->first;
    }
}

// access(u)：把 u 到当前根的路径变成实链，途中维护虚实子树集合
void access(int u) {
    int last = 0;
    for (int x = u; x != 0; x = fa[x]) {
        splay(x);
        int old_right = son[x][1];
        if (old_right != 0) {
            add_virtual(x, old_right);
        }
        if (last != 0) {
            remove_virtual(x, last);
        }
        son[x][1] = last;
        if (last != 0) {
            fa[last] = x;
        }
        pull(x);
        last = x;
    }
    splay(u);
}

// 换根：access 后翻转整条实链使 u 成为根
void make_root(int u) {
    access(u);
    apply_reverse(u);
}

// 加边 u-v：先换根再挂到 v 的虚子树
void link_tree(int u, int v) {
    make_root(u);
    access(v);
    add_virtual(v, u);
    fa[u] = v;
    pull(v);
}

// 删边 u-v：换根后这条边位于 v 实链最左侧，直接断开
void cut_tree(int u, int v) {
    make_root(u);
    access(v);
    // The edge u-v is now the leftmost edge of v's preferred path.
    if (son[v][0] == u) {
        son[v][0] = 0;
        fa[u] = 0;
        pull(v);
    }
}

// 以 root 为根时，整个树的基本费用：必须包含根的最大连通权和
long long query_root_value(int root) {
    make_root(root);
    access(root);
    long long answer = value_weight[root] + virtual_sum[root];
    return answer;
}

// 以 root 为根、只看 u 子树：允许游客从子树内任意点进入，取 G_u 与 F_u 的较大者
long long query_subtree_value(int root, int u) {
    make_root(root);
    access(u);
    long long containing = value_weight[u] + virtual_sum[u];
    long long anywhere = max(containing, virtual_best[u]);
    return anywhere;
}

// 修改节点权值并更新受影响矩阵
void modify_weight(int u, long long value) {
    access(u);
    value_weight[u] = value;
    pull(u);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> value_weight[i];
        virtual_best[i] = NEG;
        pull(i);
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        link_tree(u, v);
    }

    int current_root = 1;
    cout << query_root_value(current_root) << '\n';
    for (int i = 0; i < m; i++) {
        int type;
        cin >> type;
        if (type == 1) {
            int u;
            cin >> u;
            cout << query_subtree_value(current_root, u) << '\n';
        } else if (type == 2) {
            int u;
            long long x;
            cin >> u >> x;
            modify_weight(u, x);
            cout << query_root_value(current_root) << '\n';
        } else if (type == 3) {
            cin >> current_root;
            cout << query_root_value(current_root) << '\n';
        } else {
            int a, b, c, d;
            cin >> a >> b >> c >> d;
            cut_tree(a, b);
            link_tree(c, d);
            cout << query_root_value(current_root) << '\n';
        }
    }
    return 0;
}

复杂度

每次操作均摊 $O(\log n)$ 次 Splay 旋转，加上虚子树 multiset 的 $O(\log n)$ ，总均摊复杂度 $O(\log^2 n)$ ；空间复杂度 $O(n)$ 。

总结

把树形 DP 看作"一个节点对其路径孩子状态的函数"，就可以用 max-plus 矩阵在动态树路径上复合。Link-Cut Tree 天然只维护实链，虚子树部分用可删除的有序集合补全，就同时支持换根、点权和动态加删边。

题目来自第 37 次 CSP 认证 T5，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： 2.5 秒

空间限制： 512 MB

题目背景

西西艾弗岛上的西埃斯公园正在进行收费标准评估。

题目描述

西埃斯公园内建有 $n$ 个景点，编号为 $1,2,\cdots,n$ ，其中第 $i$ 号景点的收费为 $a_i$ 。特别地，为鼓励居民入园游览，部分景点可能有打卡领红包活动，因此 $a_i$ 可能是负数。全部景点由 $n-1$ 条可以双向通行的道路连通，因此园区路线图可以看作是一个具有 $n$ 个节点的树。

每天园区中会有一个景点举办演出，为了方便描述景点间的远近关系，我们不妨称该景点为整棵树的根节点。初始时，1 号景点为演出景点（根节点）。这样，景点 $u$ 的子树即为：从 $u$ 出发，向着远离根节点方向前进可以到达的所有景点（包含 $u$ 自身）。

游客可以从任意景点入园游览。当游客从景点 $u$ 入园时，由于可以沿着园区内的双向道路反复行走，该次游览到达的所有景点是一个包含节点 $u$ 的连通区域。当游览结束时，公园将根据游客到达的景点进行收费，每个到达的景点计费一次（即使多次到达）。该次游览的总费用即为到达的所有景点费用 $a_i$ 之和。

由于西埃斯公园是西西艾弗岛的非盈利机构，园区收费必须设置在合理水平——既能维持公园运营、也能便于居民入园游览。园区的基本费用就是一项重要的评估指标，具体定义为：游客从演出景点（根节点）入园游览一次可能的最大花费。

公园管理部门希望开发一套评估系统，该系统将首先计算一次基本费用，然后处理如下四种操作：

$1~u$ ：假设当日园区只开放景点 $u$ 的子树区域（游客只能在该区域入园、游览），计算游客从任意景点入园游览一次的最大花费。该操作只为评估收费水平，并没有真正关闭部分区域，对后续操作无影响。
$2~u~x$ ：将景点 $u$ 的收费 $a_u$ 调整为 $x$ ，然后重新计算基本费用。
$3~u$ ：将演出景点（根节点）更改为景点 $u$ ，然后重新计算基本费用。
$4~a~b~c~d$ ：园区道路施工，将原本连接景点 $a$ 和 $b$ 的道路取消，并新建一条连接景点 $c$ 和 $d$ 的双向道路，然后重新计算基本费用。保证操作前道路 $a-b$ 存在，道路 $c-d$ 不存在，且操作后园区整体仍为一棵树。

你的任务就是帮助西埃斯公园开发这套评估系统。

输入格式

从标准输入读入数据。

输入第一行：两个正整数 $n,m$ ，分别表示西埃斯公园的景点数与评估系统待处理的操作数。

输入第二行： $n$ 个整数 $a_i$ ，表示初始时每个景点的收费（可能是负数）。

接下来 $n-1$ 行：每行 2 个正整数 $u,v$ ，表示初始时有一条连接景点 $u$ 和 $v$ 的双向道路。

接下来 $m$ 行：每行 2 到 5 个整数，描述一个操作。

输出格式

输出到标准输出。

输出 $m+1$ 行，每行一个整数，分别表示初始时的基本费用及每次操作的计算结果。

input1

1
2
3
4
5
6
7
8
9
105 4
-5 7 9 -3 1
1 2
1 4
2 3
4 5
1 1
3 2
2 5 7
4 5 4 1 5

output1

样例 1 解释

初始时西埃斯公园的路线图如下，其中道路的箭头是从靠近根的景点指向远离根的景点（仅用于指示方位、道路均可双向通行）。节点内部数字为景点编号，右侧数字为该景点的收费。初始时，从景点 1 出发，选择游览 1,2,3 号景点可导致最大花费 $(-5)+7+9=11$ 。

查询当仅景点 1 的子树区域开放时（即全部景点开放）一次游览的最大花费。这种情况下，选择游览 2,3 号景点可导致最大花费 $7+9=16$ 。
将演出景点改至景点 2，西埃斯公园整体结构变为下图。此时从景点 2 出发，选择游览 2,3 号景点可导致最大花费 7+9=16。

将景点 5 的收费改为 7。此时从景点 2 出发，由于参观景点 5 必须经过 1,4 号景点，仍然是选择游览 2,3 号景点可导致最大花费 $7+9=16$ 。

园区道路施工，连接 4,5 号景点的道路取消，并在 1,5 号景点间连接一条新的双向道路，西埃斯公园整体结构变为下图。此时从 2 号景点出发，选择游览 1,2,3,5 号景点可导致最大花费 $(-5)+7+9+7=18$ 。

子任务

所有数据保证：

$1\le n,m\le 10^5$ ；
$-10^9\le a_i,x\le 10^9$ ；
$1\le u,v,a,b,c,d\le n$ ，输入道路时有 $u\ne v,~a\ne b,~c\ne d$ ；
初始时及园区道路施工后，所有景点通过双向道路构成一棵树。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

子任务编号	分值	$n,m\le$	特殊性质
1	15	$3000$	A
2	15	$10^5$	A,B
3	40	$10^5$	A
4	30	$10^5$	无

特殊性质 A：只包含操作 1,2；
特殊性质 B：1 号景点到其它任意景点的简单路径上至多包含 100 个景点。

提示

需要注意，景点费用可能为负数。

因为一次游览至少到访一个景点，所以计算结果也可能为负数。