[ZJOI2008] 树的统计

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

用树链剖分把树上路径拆成若干个 DFS 序区间，再在线段树中同时维护区间和与区间最大值。

OJ: luogu

题目 ID: P2590

难度:提高+/省选-

标签:树链剖分线段树dfs序树区间最大值

创建: 2026-06-21 03:09

更新: 2026-10-29 16:30

后置题目

roj 1564「一本通 4.5 练习 4」旅行B 的 path_spans 在代码里直接复用 A 教的「树链剖分把路径拆成连续 dfn 区间」这一步（同款选链顶较深一侧摘段再跳父亲），再叠加 A 未教的按信仰切分状态、成员 dfn 位置表二分转秩区间，以及树状数组求和/线段树求最大值，属于在树剖模板上叠加多流程的综合题。roj 1562软件包管理器B 的 install 直接复用 A 教的树链剖分拆路径方法，沿链头把根到 x 拆成连续区间逐段赋值，只是把 A 的区间查询换成带懒标记的区间赋值 shumeng CSP202509D造题计划（上）B 复用 A 的树链剖分拆 dfn 区间步骤，把路径拆成区间组后扫相邻空隙用线段树求路径补集最小 mex

题意

给出一棵带点权的树，支持三种操作：

单点修改权值
查询两点路径上的最大点权
查询两点路径上的点权和

思路

先看一个可以直接验证想法的朴素解：

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 30000 + 5;

int n;
vector<int> g[MAXN];
int val[MAXN];
int parent_arr[MAXN];
int depth_arr[MAXN];

void build_parent() {
    queue<int> q;
    q.push(1);
    parent_arr[1] = 0;
    depth_arr[1] = 1;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : g[u]) {
            if (v == parent_arr[u]) {
                continue;
            }
            parent_arr[v] = u;
            depth_arr[v] = depth_arr[u] + 1;
            q.push(v);
        }
    }
}

long long query_path_sum(int u, int v) {
    long long ans = 0;
    while (depth_arr[u] > depth_arr[v]) {
        ans += val[u];
        u = parent_arr[u];
    }
    while (depth_arr[v] > depth_arr[u]) {
        ans += val[v];
        v = parent_arr[v];
    }
    while (u != v) {
        ans += val[u] + val[v];
        u = parent_arr[u];
        v = parent_arr[v];
    }
    ans += val[u];
    return ans;
}

int query_path_max(int u, int v) {
    int ans = -30000;
    while (depth_arr[u] > depth_arr[v]) {
        ans = max(ans, val[u]);
        u = parent_arr[u];
    }
    while (depth_arr[v] > depth_arr[u]) {
        ans = max(ans, val[v]);
        v = parent_arr[v];
    }
    while (u != v) {
        ans = max(ans, val[u]);
        ans = max(ans, val[v]);
        u = parent_arr[u];
        v = parent_arr[v];
    }
    ans = max(ans, val[u]);
    return ans;
}

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

    // 这是一个朴素做法：
    // 每次查询都直接沿父亲往上跳，适合小数据对拍。
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        cin >> val[i];
    }

    build_parent();

    int q;
    cin >> q;
    while (q--) {
        string op;
        int u, v;
        cin >> op >> u >> v;
        if (op[1] == 'H') {
            val[u] = v;
        } else if (op[1] == 'M') {
            cout << query_path_max(u, v) << '\n';
        } else {
            cout << query_path_sum(u, v) << '\n';
        }
    }

    return 0;
}

brute.cpp 直接沿父亲链往上跳，直到两点相遇。这个方法完全正确，但如果树退化成链，一次查询可能要走 $O(n)$ 个点。

这题的核心是把树上路径转成区间问题。

树链剖分后：

每个点有一个 dfn
同一条重链在 DFS 序里是连续区间

于是任意路径都能拆成若干个连续区间。

接下来再用线段树维护这些区间的信息即可。

因为题目同时需要：

路径和
路径最大值

所以在线段树每个节点里同时维护：

区间和
区间最大值

CHANGE 做单点修改。

QSUM 查询路径时，把各段区间和累加起来。

QMAX 查询路径时，把各段区间最大值再取最大。

要特别注意一点：

这题点权可能为负数，所以路径最大值查询的初值不能写成 0，必须是一个足够小的负数。

本题沿用 rbook 模板 hld 的全局数组加普通函数写法，代码分成两段：

sgt 段：线段树维护 base[1..n]，支持单点修改、区间和、区间最大值
hld 段：fa / dep / sz / son / top / dfn 描述树结构，a 存原树点权，base[t] = a[dfn 位置] 是按 dfn 重排后的数组，线段树建在 base 上

n 直接在 main 里读入；build(1) 用 dfs1 递归求 fa / dep / sz / son，再用 dfs2 按"重儿子优先"分配 dfn 与链头 top，最后建树。

本题不给根，根固定为 1。线段树只有单点改（CHANGE），不需要懒标记，所以模板里的 apply / pushdown / range_add 都裁掉了，只留 push_up；两个查询沿用模板的四分式骨架，最大值分支之间用全局的 NEG_INF 做初值，这样负权点也不会被 0 偷袭。

代码

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/**
 * 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-06-21 03:09
 * update_at: 2026-10-29 16:26
 */
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// 树链剖分（HLD）+ 线段树（区间和 + 区间最大值），节点与区间均为 1 下标。
// 参考 rbook 模板 hld 的全局数组 + 普通函数写法。
// 本题特点：
//   - 不取模
//   - 只有单点修改（CHANGE），线段树不需要懒标记
//   - 同时维护区间和与区间最大值
//   - 点权可为负，查询最大值时必须用足够小的初值

const int maxn = 30000 + 5;
const ll NEG_INF = -(1LL << 60); // 点权可能为负，路径最大值查询的初值

int n;

/*------------------------ sgt 代码 开始 ------------------------*/
// 线段树：维护数组 base[1..n]，支持单点修改、区间和、区间最大值。
ll base[maxn];
ll tr[maxn << 2]; // 区间和
ll mx[maxn << 2]; // 区间最大值

int ls(int p) { return p << 1; }
int rs(int p) { return p << 1 | 1; }

// 用左右儿子的信息更新 p
void push_up(int p) {
    tr[p] = tr[ls(p)] + tr[rs(p)];
    mx[p] = max(mx[ls(p)], mx[rs(p)]);
}

void seg_build(int p, int l, int r) {
    if (l == r) {
        tr[p] = base[l];
        mx[p] = base[l];
        return;
    }
    int mid = (l + r) >> 1;
    seg_build(ls(p), l, mid);
    seg_build(rs(p), mid + 1, r);
    push_up(p);
}

// 单点修改：把 dfn 位置 pos 的值改为 value
void point_update(int pos, ll value, int p, int l, int r) {
    if (l == r) {
        tr[p] = value;
        mx[p] = value;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) point_update(pos, value, ls(p), l, mid);
    else point_update(pos, value, rs(p), mid + 1, r);
    push_up(p);
}

// 区间和
ll range_sum(int ql, int qr, int p, int l, int r) {
    if (qr < l || r < ql) return 0;
    if (ql <= l && r <= qr) return tr[p];
    int mid = (l + r) >> 1;
    ll answer = range_sum(ql, qr, ls(p), l, mid);
    answer += range_sum(ql, qr, rs(p), mid + 1, r);
    return answer;
}

// 区间最大值（不相交返回 NEG_INF）
ll range_max(int ql, int qr, int p, int l, int r) {
    if (qr < l || r < ql) return NEG_INF;
    if (ql <= l && r <= qr) return mx[p];
    int mid = (l + r) >> 1;
    ll answer = range_max(ql, qr, ls(p), l, mid);
    answer = max(answer, range_max(ql, qr, rs(p), mid + 1, r));
    return answer;
}
/*------------------------ sgt 代码 结束 ------------------------*/

/*------------------------ hld 代码 开始 ------------------------*/
// 树链剖分：g 存树，a 存原点权，6 个核心数组维护树上信息。
vector<int> g[maxn];
ll a[maxn];

int fa[maxn];  // fa[u]：父亲，根的 fa 为 0
int dep[maxn]; // dep[u]：深度，根为 1
int sz[maxn];  // sz[u]：子树大小（含自己）
int son[maxn]; // son[u]：重儿子，叶子为 0
int top[maxn]; // top[u]：所在重链的链头
int dfn[maxn]; // dfn[u]：线段树上的位置（DFS 新编号）
int timer;

void add_edge(int u, int v) {
    g[u].push_back(v);
    g[v].push_back(u);
}

// 第一遍 DFS：往下求 fa、dep，回溯时汇总 sz 并选出重儿子 son
void dfs1(int u, int father) {
    fa[u] = father;
    dep[u] = dep[father] + 1; // 根的 father 为 0、dep[0] 恒为 0，故根深度为 1
    sz[u] = 1;                // 先算上自己
    son[u] = 0;               // 叶子没有重儿子
    for (int v : g[u]) {
        if (v == father) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[v] > sz[son[u]]) son[u] = v;
    }
}

// 第二遍 DFS：重儿子优先分配 dfn，保证重链连续
void dfs2(int u, int head) {
    top[u] = head;
    dfn[u] = ++timer;
    base[timer] = a[u]; // 把点权搬到 sgt 段的数组上，线段树维护的就是它
    if (son[u]) dfs2(son[u], head);
    for (int v : g[u]) {
        if (v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}

// 预处理入口：加完边之后调用一次。其余数组在 dfs1 / dfs2 / seg_build 里逐点覆写。
void build(int root) {
    dfs1(root, 0);      // 填 fa / dep / sz / son
    timer = 0;          // 从 1 重新分配 dfn
    dfs2(root, root);   // 填 top / dfn / base
    seg_build(1, 1, n); // 交给 sgt 段
}

// 路径 (u, v) 上所有点的和。
// 不在同一条重链时，处理“链头更深”那一侧的整段 [dfn[top[u]], dfn[u]]，
// 然后 u 跳到链头的父亲。每条轻边都让子树大小至少翻倍，所以最多跳 O(log n) 次。
ll path_sum(int u, int v) {
    ll answer = 0;
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        answer += range_sum(dfn[top[u]], dfn[u], 1, 1, n);
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    answer += range_sum(dfn[u], dfn[v], 1, 1, n);
    return answer;
}

// 路径 (u, v) 上所有点的最大值。跳链过程与 path_sum 完全一致。
ll path_max(int u, int v) {
    ll answer = NEG_INF;
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        answer = max(answer, range_max(dfn[top[u]], dfn[u], 1, 1, n));
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    answer = max(answer, range_max(dfn[u], dfn[v], 1, 1, n));
    return answer;
}
/*------------------------ hld 代码 结束 ------------------------*/

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

    cin >> n;

    for (int u = 1; u <= n; ++u) g[u].clear();

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
    }
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    build(1); // 根固定为 1

    int q;
    cin >> q;
    while (q--) {
        string op;
        int u, v;
        cin >> op >> u >> v;

        if (op[1] == 'H') {
            // CHANGE u t : 单点修改
            a[u] = v;
            point_update(dfn[u], v, 1, 1, n);
        } else if (op[1] == 'M') {
            // QMAX u v
            cout << path_max(u, v) << '\n';
        } else {
            // QSUM u v
            cout << path_sum(u, v) << '\n';
        }
    }

    return 0;
}

复杂度

预处理和建树是 $O(n)$ 。

单点修改是 $O(\log n)$ 。

每次路径查询会被拆成 $O(\log n)$ 段，所以 QSUM 和 QMAX 的复杂度都是 $O(\log^2 n)$ 。

空间复杂度是 $O(n)$ 。

总结

这题是很标准的树链剖分模板题。

关键是两步：

先把树上路径拆成若干个 DFS 序连续区间
再在线段树上维护这些区间的统计信息

而且要记住负权这个细节，否则 QMAX 很容易写错。

P2590 [ZJOI2008] 树的统计

题目描述

一棵树上有 $n$ 个节点，编号分别为 $1$ 到 $n$ ，每个节点都有一个权值 $w$ 。

我们将以下面的形式来要求你对这棵树完成一些操作：

I. CHANGE u t : 把结点 $u$ 的权值改为 $t$ 。

II. QMAX u v: 询问从点 $u$ 到点 $v$ 的路径上的节点的最大权值。

III. QSUM u v: 询问从点 $u$ 到点 $v$ 的路径上的节点的权值和。

注意：从点 $u$ 到点 $v$ 的路径上的节点包括 $u$ 和 $v$ 本身。

输入格式

输入文件的第一行为一个整数 $n$ ，表示节点的个数。

接下来 $n-1$ 行，每行 $2$ 个整数 $a$ 和 $b$ ，表示节点 $a$ 和节点 $b$ 之间有一条边相连。

接下来一行 $n$ 个整数，第 $i$ 个整数 $w_i$ 表示节点 $i$ 的权值。

接下来 $1$ 行，为一个整数 $q$ ，表示操作的总数。

接下来 $q$ 行，每行一个操作，以 CHANGE u t 或者 QMAX u v 或者 QSUM u v 的形式给出。

输出格式

对于每个 QMAX 或者 QSUM 的操作，每行输出一个整数表示要求输出的结果。

输入输出样例 #1

输入 #1

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
184
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4

输出 #1

text

说明/提示

对于 $100 \%$ 的数据，保证 $1\le n \le 3\times 10^4$ ， $0\le q\le 2\times 10^5$ 。

中途操作中保证每个节点的权值 $w$ 在 $-3\times 10^4$ 到 $3\times 10^4$ 之间。

[ZJOI2008] 树的统计

目录

题意

思路

代码

复杂度

总结