[HAOI2015] 树上操作

形式化题目

有一棵以 $1$ 为根、带点权的树，支持三类操作：

节点 $x$ 点权增加 $a$ ；
以 $x$ 为根的子树内所有点权增加 $a$ ；
询问 $x$ 到根 $1$ 路径上的点权和。

按顺序处理 $m$ 次操作，输出所有询问的答案。

思路

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

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/**
 * 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-08-12 23:00
 * update_at: 2026-08-12 23:00
 */
// brute.cpp：小数据暴力解，直接模拟三种操作，用来理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int n, m;
long long w[MAXN];       // w[i] 表示节点 i 当前的权值
int parent[MAXN];        // 预处理出的父亲
vector<int> g[MAXN];     // 树的邻接表

// 以 u 为根的子树整体加 value（u 是根节点 1，fa 用来防止回头走）。
void subtree_add(int u, int fa, long long value) {
    w[u] += value;
    for (int j = 0; j < (int)g[u].size(); j++) {
        int v = g[u][j];
        if (v != fa) subtree_add(v, u, value);
    }
}

// 求从 x 走到根 1 的路径点权和：不断沿 parent 上跳累加。
long long root_path_sum(int x) {
    long long answer = 0;
    while (x != 0) {
        answer += w[x];
        x = parent[x];
    }
    return answer;
}

// 预处理 parent：从根 1 出发遍历整棵树。
void build_parent(int u, int fa) {
    parent[u] = fa;
    for (int j = 0; j < (int)g[u].size(); j++) {
        int v = g[u][j];
        if (v != fa) build_parent(v, u);
    }
}

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

    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> w[i];
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    build_parent(1, 0);

    while (m--) {
        int opt, x;
        long long a;
        cin >> opt >> x;
        if (opt == 1) { // 单点加
            cin >> a;
            w[x] += a;
        } else if (opt == 2) { // 子树整体加：递归访问子树所有点
            cin >> a;
            subtree_add(x, parent[x], a);
        } else { // 询问根路径和：沿 parent 一路加到根
            cout << root_path_sum(x) << '\n';
        }
    }

    return 0;
}

brute.cpp 完全按题意模拟：操作 2 递归遍历整棵子树逐点加，操作 3 沿 parent 一路累加到根，单次操作最坏 $O(n)$ ，总复杂度 $O(nm)$ ，无法通过 $10^5$ 的数据。

两个关键观察把树结构操作变成序列区间操作：

子树是 DFS 序上的连续区间：给每个节点分配 DFS 进入编号 $dfn$ 后，节点 $x$ 的子树恰好是 $[dfn[x],\ dfn[x]+sz[x]-1]$ 。于是"子树整体加"变成"数组区间加"。
根路径能拆成 $O(\log n)$ 段连续区间：普通 DFS 序上路径不连续，但树链剖分让每条重链编号连续，根到 $x$ 的路径被拆成 $O(\log n)$ 条重链段，每段都是连续区间。

以样例的树为例（边为 $1\text{-}2, 1\text{-}4, 2\text{-}3, 2\text{-}5$ ），剖分后各节点的映射如下：

节点 $x$	1	2	3	4	5
$dfn[x]$	1	2	3	5	4
子树区间	[1,5]	[2,4]	[3,3]	[5,5]	[4,4]
链头 $top[x]$	1	1	1	4	5

观察表格：节点 2 的子树 $\{2,3,5\}$ 正好是区间 $[2,4]$ ；询问节点 5 到根的路径时，先取链头 5 的区间 $[4,4]$ ，再跳到链头 1 所在链取 $[1,2]$ ，两段区间覆盖了路径 $\{5\} \cup \{1,2\}$ 。

区间操作需要"区间加 + 区间和"，用 rbook 模板 fenwick-range-add-sum 的双树状数组：差分数组上区间加只改两个端点，而前缀和

P(x)=(x+1)\sum_{j=1}^{x}b_j-\sum_{j=1}^{x}j\cdot b_j

需要维护 $\sum b_j$ 与 $\sum j\cdot b_j$ 两个动态前缀和，正好是两棵树。

代码

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/**
 * 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-08-12 23:00
 * update_at: 2026-08-12 23:00
 */
// main.cpp：P3178 树上操作，树链剖分 + 双树状数组（区间加、区间和）。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n, m;
long long w[MAXN];       // 每个点的初始权值
vector<int> g[MAXN];     // 树的邻接表

// 树链剖分相关数组
int parent[MAXN];    // 父亲
int depth[MAXN];     // 深度，根为 1
int sz[MAXN];        // 子树大小
int heavy[MAXN];     // 重儿子（子树最大的儿子）
int top[MAXN];       // 重链链头
int dfn[MAXN];       // DFS 新编号 1..n
int timer;           // dfn 分配计数器
int order[MAXN];     // 第一次遍历得到的节点顺序
int order_cnt;       // order 的长度

// 仿 rbook 模板 fenwick-range-add-sum：双树状数组，区间加、区间和。
// bit_diff 维护差分 b[i]，bit_weighted 维护 i * b[i]。
template <typename T>
struct RangeFenwick {
    int n = 0;
    vector<T> bit_diff, bit_weighted;

    RangeFenwick(int n = 0) { init(n); }

    void init(int size) {
        n = size;
        bit_diff.assign(n + 1, 0);
        bit_weighted.assign(n + 1, 0);
    }

    static int lowbit(int x) { return x & -x; }

    void add(vector<T> &bit, int pos, T value) {
        for (int i = pos; i <= n; i += lowbit(i)) {
            bit[i] += value;
        }
    }

    T sum(const vector<T> &bit, int pos) const {
        T answer = 0;
        for (int i = pos; i > 0; i -= lowbit(i)) {
            answer += bit[i];
        }
        return answer;
    }

    // 原数组区间 [left, right] 每个位置都加上 value
    void range_add(int left, int right, T value) {
        add(bit_diff, left, value);
        add(bit_diff, right + 1, -value);
        add(bit_weighted, left, value * static_cast<T>(left));
        add(bit_weighted, right + 1, -value * static_cast<T>(right + 1));
    }

    // 原数组前缀和：P(pos) = (pos+1) * sum(b, pos) - sum(i*b, pos)
    T prefix_sum(int pos) const {
        return static_cast<T>(pos + 1) * sum(bit_diff, pos)
             - sum(bit_weighted, pos);
    }

    T range_sum(int left, int right) const {
        return prefix_sum(right) - prefix_sum(left - 1);
    }
};

RangeFenwick<long long> bit;

// 第一遍：按 BFS 顺序求 parent/depth，并逆序统计子树大小、选出重儿子。
void build_hld() {
    order_cnt = 0;
    order[++order_cnt] = 1;
    parent[1] = 0;
    depth[1] = 1;
    for (int i = 1; i <= order_cnt; i++) {
        int u = order[i];
        for (int j = 0; j < (int)g[u].size(); j++) {
            int v = g[u][j];
            if (v == parent[u]) continue;
            parent[v] = u;
            depth[v] = depth[u] + 1;
            order[++order_cnt] = v;
        }
    }
    for (int i = 1; i <= n; i++) sz[i] = 1;
    for (int i = order_cnt; i >= 2; i--) {
        int u = order[i];
        sz[parent[u]] += sz[u];
        if (sz[u] > sz[heavy[parent[u]]]) heavy[parent[u]] = u;
    }
}

// 第二遍：用链栈分配 dfn，保证每条重链编号连续、子树编号连续。
void build_dfn() {
    timer = 0;
    vector<pair<int, int>> chain_stack; // (当前节点, 所在链头)
    chain_stack.push_back(make_pair(1, 1));
    while (!chain_stack.empty()) {
        int u = chain_stack.back().first;
        int chain_top = chain_stack.back().second;
        chain_stack.pop_back();
        while (u != 0) {
            top[u] = chain_top;
            dfn[u] = ++timer;
            // 轻儿子开新链入栈，重儿子继续沿当前链走。
            for (int j = 0; j < (int)g[u].size(); j++) {
                int v = g[u][j];
                if (v != parent[u] && v != heavy[u]) {
                    chain_stack.push_back(make_pair(v, v));
                }
            }
            u = heavy[u];
        }
    }
}

// 查询从 x 到根 1 的路径点权和：拆成若干重链区间求和。
long long root_path_sum(int x) {
    long long answer = 0;
    while (top[x] != top[1]) {
        answer += bit.range_sum(dfn[top[x]], dfn[x]);
        x = parent[top[x]];
    }
    answer += bit.range_sum(dfn[1], dfn[x]);
    return answer;
}

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

    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> w[i];
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    build_hld();
    build_dfn();

    bit.init(n);
    // 初始权值：每个 dfn 位置单独区间加。
    for (int i = 1; i <= n; i++) {
        bit.range_add(dfn[i], dfn[i], w[i]);
    }

    while (m--) {
        int opt, x;
        long long a;
        cin >> opt >> x;
        if (opt == 1) { // 单点加：区间加退化为单点
            cin >> a;
            bit.range_add(dfn[x], dfn[x], a);
        } else if (opt == 2) { // 子树加：子树在 dfn 上是连续区间
            cin >> a;
            bit.range_add(dfn[x], dfn[x] + sz[x] - 1, a);
        } else { // 根路径和：重链区间求和
            cout << root_path_sum(x) << '\n';
        }
    }

    return 0;
}

复杂度

预处理：两次遍历 $O(n)$ ，初始权值入树状数组 $O(n \log n)$ 。
操作 1 / 2：一次区间加 $O(\log n)$ 。
操作 3：至多 $O(\log n)$ 段重链，每段区间和 $O(\log n)$ ，总 $O(\log^2 n)$ 。
空间：邻接表、HLD 数组与两棵 Fenwick 均 $O(n)$ 。

总结

这道题的套路是把树结构操作"映射"到数组上：DFS 序让子树变连续区间，树链剖分让根路径变成 $O(\log n)$ 段连续区间，之后所有修改与查询都只是区间加、区间和，交给双树状数组即可。rbook 的《树链剖分》讲解了重链连续编号与路径拆段，以及本解使用的 hld 模板；《双树状数组：区间修改与区间查询》推导了本解 RangeFenwick 的两树前缀和公式（模板 fenwick-range-add-sum）。

图示解析

这张 ASCII 图展示整道题的解题路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19朴素模拟（brute.cpp）
  单点加 O(1)；子树逐点加、根路径逐点累加  O(n) 每次操作
        |
        | 瓶颈：子树与路径不是数组区间，m 次操作 O(n*m) 太大
        v
关键观察（两种映射）
  DFS 序：子树 x = [dfn[x], dfn[x] + sz[x] - 1]    连续区间
  树链剖分：根到 x 的路径 = O(log n) 条重链段      每段连续
        |
        v
双树状数组（main.cpp）
  区间加：差分只改 l、r+1 两个端点
  区间和：P(x) = (x+1)*sum(b) - sum(i*b)
  操作1: 区间加 [dfn[x], dfn[x]]
  操作2: 区间加 [dfn[x], dfn[x]+sz[x]-1]
  操作3: 沿重链跳，逐段区间和
        |
        v
复杂度 O(n log n + m log^2 n)，空间 O(n)

图中两条主线对应"暴力慢在哪"“树结构如何变成区间”。核心是：只要子树和路径都能用少量连续区间表示，三种操作就全部退化为序列上的区间加与区间和。