「一本通 4.5 例 1」树的统计

形式化题目

给定一棵包含 $n$ 个节点的带点权无向树。要求支持以下三种在线操作：

单点修改：将节点 $u$ 的权值更新为 $t$ ；
路径最大值查询：求节点 $u$ 到节点 $v$ 的简单路径上所有节点权值的最大值；
路径和查询：求节点 $u$ 到节点 $v$ 的简单路径上所有节点权值的总和。

正解

思路

对于树上路径的动态修改与统计问题，若直接进行暴力搜索或 DFS/BFS 遍历，单次查询最坏需要遍历整棵树，时间复杂度为 $\mathcal{O}(n)$ ，在 $q = 2\times 10^5$ 的操作规模下必然超时。

为了高效支持树上路径修改与查询，我们采用重链剖分（树链剖分）将树上节点重新编号，把树上路径拆解为 $\mathcal{O}(\log n)$ 段连续的区间，随后使用底层的线段树进行维护：

两遍遍历（树链剖分）：
- 第一次遍历：确定每个节点的深度 depth、父节点 parent、子树大小 size 以及重儿子 heavy（即子树规模最大的子节点）。
- 第二次遍历：优先访问重儿子，建立每个节点的 DFS 序（dfn）和所属重链的链顶（top）。由于重儿子被连续遍历，同一条重链上的所有节点在 DFS 序中对应一段连续的整数区间。
路径查询与拆分：
- 设当前查询路径两端点为 $u$ 和 $v$ 。若 $u$ 和 $v$ 不在同一条重链上（top[u] != top[v]），不妨设深度较深的链顶为 $u$ ，则节点 $u$ 到其链顶 top[u] 是一段连续的 DFS 区间 $[\mathrm{dfn}[\mathrm{top}[u]], \mathrm{dfn}[u]]$ ，在线段树中查询这一区间的统计信息，然后将 $u$ 跃迁至其链顶的父节点 $u \leftarrow \mathrm{parent}[\mathrm{top}[u]]$ 。
- 重复上述过程，直到 $u$ 与 $v$ 跃迁至同一条重链上。此时两点之间的路径同样对应一段连续区间 $[\min(\mathrm{dfn}[u], \mathrm{dfn}[v]), \max(\mathrm{dfn}[u], \mathrm{dfn}[v])]$ ，在线段树中再做一次区间查询即可。
- 由于任意节点到根节点的路径至多经过 $\mathcal{O}(\log n)$ 条轻边（即被拆分成 $\mathcal{O}(\log n)$ 段重链区间），单次路径查询的复杂度为 $\mathcal{O}(\log^2 n)$ 。
底层线段树维护：
- 线段树每个节点维护对应区间的权值和 sum 与最大值 max。
- 单点修改只需更新叶子节点 $\mathrm{dfn}[u]$ ，自底向上合并信息，复杂度为 $\mathcal{O}(\log n)$ 。

代码

Python 版：

python

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#!/usr/bin/env python3
# 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-09-30 18:15
# update_at: 2026-09-30 18:15

import sys

INF = 10**9


def build_tree_layout(n: int, adj: list[list[int]], root: int = 1) -> tuple[list[int], list[int], list[int], list[int]]:
    """以非递归遍历剖分树链，返回父节点、深度、重链顶与 DFS 序映射。"""
    parent = [0] * (n + 1)
    depth = [0] * (n + 1)
    heavy = [0] * (n + 1)
    size = [1] * (n + 1)

    order: list[int] = []
    stack = [root]
    depth[root] = 1
    while stack:
        u = stack.pop()
        order.append(u)
        for v in adj[u]:
            if v != parent[u]:
                parent[v] = u
                depth[v] = depth[u] + 1
                stack.append(v)

    # 倒序回溯计算子树大小及重儿子
    for u in reversed(order):
        heavy_child, max_s = 0, 0
        for v in adj[u]:
            if v != parent[u]:
                size[u] += size[v]
                if size[v] > max_s:
                    max_s = size[v]
                    heavy_child = v
        heavy[u] = heavy_child

    # 二次遍历确定重链顶与 DFS 序
    top = [0] * (n + 1)
    dfn = [0] * (n + 1)
    timer = 0
    stack = [(root, root)]
    while stack:
        u, chain_top = stack.pop()
        timer += 1
        dfn[u] = timer
        top[u] = chain_top

        # 轻儿子先压栈，重儿子后压栈保证先访问重儿子
        for v in adj[u]:
            if v != parent[u] and v != heavy[u]:
                stack.append((v, v))
        if heavy[u]:
            stack.append((heavy[u], chain_top))

    return parent, depth, top, dfn


class SegmentTree:
    """维护区间和与区间最大值的线段树。"""

    def __init__(self, n: int, initial_weights: list[int]) -> None:
        self.size = 1
        while self.size <= n + 1:
            self.size <<= 1
        self.tree_max = [-INF] * (2 * self.size)
        self.tree_sum = [0] * (2 * self.size)
        for i, w in enumerate(initial_weights, 1):
            pos = self.size + i
            self.tree_max[pos] = w
            self.tree_sum[pos] = w
        for i in range(self.size - 1, 0, -1):
            left, right = i << 1, (i << 1) | 1
            self.tree_max[i] = max(self.tree_max[left], self.tree_max[right])
            self.tree_sum[i] = self.tree_sum[left] + self.tree_sum[right]

    def update(self, pos: int, val: int) -> None:
        """单点修改：把位置 pos 的值赋为 val。"""
        idx = self.size + pos
        self.tree_max[idx] = val
        self.tree_sum[idx] = val
        idx >>= 1
        while idx:
            left, right = idx << 1, (idx << 1) | 1
            self.tree_max[idx] = max(self.tree_max[left], self.tree_max[right])
            self.tree_sum[idx] = self.tree_sum[left] + self.tree_sum[right]
            idx >>= 1

    def query_max(self, left: int, right: int) -> int:
        """区间求最大值 [left, right]。"""
        res = -INF
        left += self.size
        right += self.size + 1
        while left < right:
            if left & 1:
                res = max(res, self.tree_max[left])
                left += 1
            if right & 1:
                right -= 1
                res = max(res, self.tree_max[right])
            left >>= 1
            right >>= 1
        return res

    def query_sum(self, left: int, right: int) -> int:
        """区间求和 [left, right]。"""
        res = 0
        left += self.size
        right += self.size + 1
        while left < right:
            if left & 1:
                res += self.tree_sum[left]
                left += 1
            if right & 1:
                right -= 1
                res += self.tree_sum[right]
            left >>= 1
            right >>= 1
        return res


def path_max(u: int, v: int, parent: list[int], depth: list[int], top: list[int], dfn: list[int], seg: SegmentTree) -> int:
    """求路径 u 到 v 上的节点权值最大值。"""
    res = -INF
    while top[u] != top[v]:
        if depth[top[u]] < depth[top[v]]:
            u, v = v, u
        res = max(res, seg.query_max(dfn[top[u]], dfn[u]))
        u = parent[top[u]]
    if depth[u] > depth[v]:
        u, v = v, u
    res = max(res, seg.query_max(dfn[u], dfn[v]))
    return res


def path_sum(u: int, v: int, parent: list[int], depth: list[int], top: list[int], dfn: list[int], seg: SegmentTree) -> int:
    """求路径 u 到 v 上的节点权值和。"""
    res = 0
    while top[u] != top[v]:
        if depth[top[u]] < depth[top[v]]:
            u, v = v, u
        res += seg.query_sum(dfn[top[u]], dfn[u])
        u = parent[top[u]]
    if depth[u] > depth[v]:
        u, v = v, u
    res += seg.query_sum(dfn[u], dfn[v])
    return res


def solve() -> None:
    raw = sys.stdin.buffer.read().split()
    if not raw:
        return
    it = iter(raw)

    n = int(next(it))
    adj: list[list[int]] = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        u = int(next(it))
        v = int(next(it))
        adj[u].append(v)
        adj[v].append(u)

    raw_weights = [0] + [int(next(it)) for _ in range(n)]

    parent, depth, top, dfn = build_tree_layout(n, adj)

    # 按照 dfn 序重排初始权值
    seg_init = [0] * n
    for u in range(1, n + 1):
        seg_init[dfn[u] - 1] = raw_weights[u]

    seg = SegmentTree(n, seg_init)

    q = int(next(it))
    out: list[str] = []

    for _ in range(q):
        op = next(it).decode()
        u = int(next(it))
        v_or_val = int(next(it))
        if op == "CHANGE":
            seg.update(dfn[u], v_or_val)
        elif op == "QMAX":
            ans = path_max(u, v_or_val, parent, depth, top, dfn, seg)
            out.append(str(ans))
        else:
            ans = path_sum(u, v_or_val, parent, depth, top, dfn, seg)
            out.append(str(ans))

    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-10-05 08:18
 * update_at: 2026-10-05 08:18
 */

// 树链剖分（重链剖分）+ 线段树，维护单点修改、路径最大值、路径和。
// 核心思想：优先遍历重儿子，使每条重链在 DFS 序上对应一段连续区间，
// 于是树上路径可拆成 O(log n) 段区间，交给线段树做单点改、区间查。

#include <cstdio>
#include <algorithm>

typedef long long ll;

const int MAXN = 30005;      // 节点数上限（n <= 3e4）
const ll  INF = 1e9;         // 权值绝对值 <= 30000，用 1e9 做无穷大足够

int n, q;
ll weight[MAXN];             // weight[u] = 节点 u 的点权

// 链式前向星存树
int head[MAXN], nxt[2 * MAXN], to[2 * MAXN], edge_cnt;
void add_edge(int u, int v) {
    edge_cnt++;
    to[edge_cnt] = v;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

// 树链剖分信息
int parent[MAXN];            // 父节点
int depth[MAXN];             // 深度，根为 1
int heavy[MAXN];             // 重儿子编号，叶子为 0
int top_[MAXN];              // 所在重链的链顶
int dfn[MAXN];               // DFS 序编号，同一条重链上的 dfn 连续
int timer_cnt;

// 线段树（按 dfn 序建）：sum 区间和，mx 区间最大值
ll sum_tree[4 * MAXN];
ll mx_tree[4 * MAXN];

// ---- 第一次遍历：求 parent、depth、size，并选重儿子 ----
// 用非递归的栈式 DFS，避免 n 较大时递归爆栈；order 保存遍历顺序供倒序算子树大小
int sta[MAXN], order[MAXN], size_[MAXN];
void dfs1(int root) {
    int top = 0, cnt = 0;
    sta[++top] = root;
    parent[root] = 0;
    depth[root] = 1;
    while (top > 0) {
        int u = sta[top];
        top--;
        cnt++;
        order[cnt] = u;
        for (int e = head[u]; e; e = nxt[e]) {
            int v = to[e];
            if (v == parent[u]) continue;
            parent[v] = u;
            depth[v] = depth[u] + 1;
            sta[++top] = v;
        }
    }
    // 倒序回溯：孩子一定先于父亲入过栈，倒序累加子树大小并选重儿子
    for (int i = cnt; i >= 1; i--) {
        int u = order[i];
        size_[u] = 1;
        for (int e = head[u]; e; e = nxt[e]) {
            int v = to[e];
            if (v == parent[u]) continue;
            size_[u] += size_[v];
            if (size_[v] > size_[heavy[u]]) heavy[u] = v;
        }
    }
}

// ---- 第二次遍历：优先走重儿子，求 dfn 和 top ----
void dfs2(int root) {
    // 栈里存 (节点, 链顶)，重儿子后压栈从而先被访问
    int top = 0;
    static int node_st[2 * MAXN];
    static int top_st[2 * MAXN];
    node_st[++top] = root;
    top_st[top] = root;
    while (top > 0) {
        int u = node_st[top];
        int t = top_st[top];
        top--;
        timer_cnt++;
        dfn[u] = timer_cnt;
        top_[u] = t;
        for (int e = head[u]; e; e = nxt[e]) {
            int v = to[e];
            if (v == parent[u] || v == heavy[u]) continue;
            top++;
            node_st[top] = v;
            top_st[top] = v;   // 轻儿子自成一条新链，链顶是它自己
        }
        if (heavy[u] != 0) {
            top++;
            node_st[top] = heavy[u];
            top_st[top] = t;   // 重儿子继承当前链顶
        }
    }
}

// ---- 线段树 ----
// 建树：pos 是 dfn 位置，叶子权值按 dfn 序排布
ll seg_val[MAXN];            // seg_val[dfn[u]] = dfn 序位置上的点权
void build(int node, int l, int r) {
    if (l == r) {
        sum_tree[node] = seg_val[l];
        mx_tree[node] = seg_val[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(node << 1, l, mid);
    build(node << 1 | 1, mid + 1, r);
    sum_tree[node] = sum_tree[node << 1] + sum_tree[node << 1 | 1];
    mx_tree[node] = std::max(mx_tree[node << 1], mx_tree[node << 1 | 1]);
}

// 单点修改：把位置 pos 的值改为 val
void update(int node, int l, int r, int pos, ll val) {
    if (l == r) {
        sum_tree[node] = val;
        mx_tree[node] = val;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) update(node << 1, l, mid, pos, val);
    else update(node << 1 | 1, mid + 1, r, pos, val);
    sum_tree[node] = sum_tree[node << 1] + sum_tree[node << 1 | 1];
    mx_tree[node] = std::max(mx_tree[node << 1], mx_tree[node << 1 | 1]);
}

ll query_sum(int node, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return sum_tree[node];
    int mid = (l + r) >> 1;
    ll res = 0;
    if (ql <= mid) res += query_sum(node << 1, l, mid, ql, qr);
    if (qr > mid) res += query_sum(node << 1 | 1, mid + 1, r, ql, qr);
    return res;
}

ll query_max(int node, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return mx_tree[node];
    int mid = (l + r) >> 1;
    ll res = -INF;
    if (ql <= mid) res = std::max(res, query_max(node << 1, l, mid, ql, qr));
    if (qr > mid) res = std::max(res, query_max(node << 1 | 1, mid + 1, r, ql, qr));
    return res;
}

// 树上路径拆链：每次跳链顶较深的一端，查 [dfn[top[u]], dfn[u]]，最后查同链一段
ll path_sum(int u, int v) {
    ll res = 0;
    while (top_[u] != top_[v]) {
        if (depth[top_[u]] < depth[top_[v]]) std::swap(u, v);
        res += query_sum(1, 1, n, dfn[top_[u]], dfn[u]);
        u = parent[top_[u]];
    }
    if (depth[u] > depth[v]) std::swap(u, v);
    res += query_sum(1, 1, n, dfn[u], dfn[v]);
    return res;
}

ll path_max(int u, int v) {
    ll res = -INF;
    while (top_[u] != top_[v]) {
        if (depth[top_[u]] < depth[top_[v]]) std::swap(u, v);
        res = std::max(res, query_max(1, 1, n, dfn[top_[u]], dfn[u]));
        u = parent[top_[u]];
    }
    if (depth[u] > depth[v]) std::swap(u, v);
    res = std::max(res, query_max(1, 1, n, dfn[u], dfn[v]));
    return res;
}

void solve() {
    scanf("%d", &n);
    for (int i = 1; i <= n - 1; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        add_edge(a, b);
        add_edge(b, a);
    }
    for (int i = 1; i <= n; i++) scanf("%lld", &weight[i]);

    dfs1(1);
    dfs2(1);
    for (int u = 1; u <= n; u++) seg_val[dfn[u]] = weight[u]; // 按 dfn 序排布点权
    build(1, 1, n);

    scanf("%d", &q);
    char op[10];
    for (int i = 1; i <= q; i++) {
        scanf("%s", op);
        int a, b;
        scanf("%d %d", &a, &b);
        if (op[0] == 'C') {
            update(1, 1, n, dfn[a], b);   // CHANGE：改 dfn[a] 位置的值
        } else if (op[1] == 'M') {
            printf("%lld\n", path_max(a, b));
        } else {
            printf("%lld\n", path_sum(a, b));
        }
    }
}

int main() {
    solve();
    return 0;
}

复杂度

时间复杂度：
- 树链剖分预处理需要两次树遍历，耗时 $\mathcal{O}(n)$ ；
- 建树耗时 $\mathcal{O}(n)$ ；
- 每次单点修改操作在线段树上单点更新，耗时 $\mathcal{O}(\log n)$ ；
- 每次路径查询（QMAX / QSUM）将路径拆解为至多 $\mathcal{O}(\log n)$ 段区间，每段区间在线段树上耗时 $\mathcal{O}(\log n)$ ，总耗时为 $\mathcal{O}(\log^2 n)$ ；
- 处理 $q$ 次操作的总时间复杂度为 $\mathcal{O}(n + q \log^2 n)$ 。
空间复杂度：
- 邻接表及树链剖分数组需 $\mathcal{O}(n)$ 空间；
- 存储树上点权的线段树需 $\mathcal{O}(n)$ 空间；
- 总体额外空间复杂度为 $\mathcal{O}(n)$ 。

总结

树链剖分（轻重链剖分）的核心思想在于：通过优先遍历重儿子，使得任意一条重链上的节点在 DFS 序上均排布在一段连续区间内。
借助这一性质，复杂的树上路径查询被转化为若干个序列区间查询，从而能够无缝结合线段树等序列数据结构高效求解。

图示解析

下图展示了样例中 4 个节点的树结构及重链划分情况。图中双线箭头表示重边组成的重链，单线箭头表示轻边。

graph TD
    classDef heavy stroke:#e74c3c,stroke-width:3px;
    classDef light stroke:#3498db,stroke-width:1.5px;

    1((1<br/>w=4))
    2((2<br/>w=2))
    3((3<br/>w=1))
    4((4<br/>w=3))

    1 ==>|重边| 2
    2 ==>|重边| 3
    1 -->|轻边| 4

    class 1,2,3 heavy;
    class 4 light;

以节点 1 为根时，子节点 2 的子树包含节点 $\{2, 3\}$ （大小为 2），节点 4 的子树仅包含自身（大小为 1），因此 $1 \to 2 \to 3$ 构成同一条连续的重链。当查询节点 3 到节点 4 的路径时：

节点 3 所在重链链顶为 1，节点 4 所在重链链顶为 4；
由于 $\mathrm{depth}[\mathrm{top}[4]] = 2 > \mathrm{depth}[\mathrm{top}[3]] = 1$ ，先处理轻链端点 4（区间 $[4, 4]$ ），随后节点 4 跳至其父节点 1；
此时节点 1 与节点 3 均在同一条重链上，直接查询区间 $[1, 3]$ ，两部分统计结果合并即可得到整条路径的答案。

「一本通 4.5 例 1」树的统计

目录

形式化题目

正解

思路

代码

复杂度

总结

图示解析