「一本通 4.5 练习 1」树上操作

形式化题目

给定一棵以点 $1$ 为根、点数为 $n$ 的树，每个点 $u$ 有权值 $w[u]$ 。维护以下三类操作：

单点加： $w[x] \mathrel{+}= a$ ；
子树加：对以 $x$ 为根的子树中每个点 $u$ ， $w[u] \mathrel{+}= a$ ；
路径询问：求根到 $x$ 的路径（即 $x$ 的全部祖先，含自身）上所有点权之和
$A[x] = \sum_{u \text{ 是 } x \text{ 的祖先}} w[u].$

题面给出的输入样例缺了首行 N M（样例按 $n=5,\ m=5$ 补全后与官方输出一致）；代码以真实测试数据的格式（首行 N M）读入。下图为样例的树（括号内为深度 $depth$ 与初始权值）：

graph TD
    n1["1: d=0, w=1"] --> n2["2: d=1, w=2"]
    n1 --> n4["4: d=1, w=4"]
    n2 --> n3["3: d=2, w=3"]
    n2 --> n5["5: d=2, w=5"]

图中每条有向边都由父亲指向孩子，深度沿边递增 1； $depth$ 之后会作为拆项公式 $a(depth[y]-depth[x]+1)$ 中的系数出现，而每个节点的子树就是它下方的整块—— 样例执行过程（只列变化部分）：

步骤	操作	说明	输出
初始	—	权值 1 2 3 4 5
1	`3 3`	路径 $1 \to 2 \to 3$ ： $1+2+3$	6
2	`1 2 1`	$w[2] \mathrel{+}= 1$ ，变为 3
3	`3 5`	路径 $1 \to 2 \to 5$ ： $1+3+5$	9
4	`2 1 2`	整棵树加 2，权值变 3 5 5 6 7
5	`3 3`	路径 $1 \to 2 \to 3$ ： $3+5+5$	13

三次询问的答案依次为 6、9、13：第 4 步整棵树加 2 后，路径上的点数（3 个）就是增量 6 的来源，正好对应下文公式中的 $depth[y]+1$ 。

正解

思路

朴素做法与瓶颈。 单点加直接改 $w[x]$ 只要 $O(1)$ ；但子树加要 DFS 整棵子树、路径询问要沿父链上溯，都是 $O(N)$ ， $n, m \leqslant 10^5$ 时最坏 $10^{10}$ 次操作，必然超时。问题的张力在于：修改的自然单位是子树，询问的自然单位是祖先链，两者在树上不重合—— 祖先链在 DFS 序中是散落的点，子树在祖先视角下是逐点枚举，硬套任何一边都会退化。

第一步：DFS 序把子树变成连续区间。 按进入时刻给节点编号 $tin$ ，则子树 $x$ 恰好对应连续区间 $[tin[x], tout[x]]$ 。样例树按"根 → 左孩子优先"进入的编号为 $1 \mapsto 1,\ 4 \mapsto 2,\ 2 \mapsto 3,\ 5 \mapsto 4,\ 3 \mapsto 5$ ，子树 $2 = [3, 5]$ 、子树 $3 = [5, 5]$ ，确实都是连续段。

第二步：换维护对象——直接维护询问答案 $A[y]$ 。 写出询问的定义式 $A[y] = \sum_{u \text{ 是 } y \text{ 的祖先}} w[u]$ ，换个读法：点 $u$ 的权值 $w[u]$ ，恰好被所有 $y \in subtree(u)$ 的询问各统计一次。于是：

单点加（ $w[x] \mathrel{+}= a$ ）：受影响的 $y$ 恰是 $subtree(x)$ ，每个 $y$ 的答案统一 $+a$ —— 区间 $[tin[x], tout[x]]$ 加 $a$ 。修改从"点"升维到"区间"，反而变规整了。

第三步：子树加拆成 depth 的一次函数。 给 $subtree(x)$ 每点加 $a$ 后， $y$ 的答案增量是 $a \times$ （ $y$ 的祖先中落在 $subtree(x)$ 内的个数）。祖先落在子树内 $\Rightarrow$ 该祖先的后代 $y$ 也在子树内，所以 $y \notin subtree(x)$ 时增量为 $0$ ； $y \in subtree(x)$ 时，这样的祖先恰是 $x \to y$ 路径上的 $depth[y] - depth[x] + 1$ 个点：

\Delta A[y] = a\,(depth[y] - depth[x] + 1) = a \cdot depth[y] + a(1 - depth[x]).

增量是 $depth[y]$ 的一次函数： $depth[y]$ 与位置有关、无法统一，但常数系数可以拆开—— "乘 $depth[y]$ 的那部分"和"纯常数部分"各自都是区间统一加。用两棵树状数组分工： $A[y] = depth[y] \cdot q_1[y] + q_2[y]$ ，其中 $q_1$ 记一次项系数、 $q_2$ 记常数项（初始权值和单点加都只贡献常数，也进 $q_2$ ）。

第四步：询问退化为点查。 三种操作落到数据结构上的动作汇总如下（区间均为 $[tin[x], tout[x]]$ ）：

操作	对 $A[y]$ 的贡献	树状数组上的动作
初始权值 $w[u]$	$y \in subtree(u)$ 时 $+w[u]$	$q_2$ 区间加 $w[u]$
1 单点加 $a$	$y \in subtree(x)$ 时 $+a$	$q_2$ 区间加 $a$
2 子树加 $a$	$y \in subtree(x)$ 时 $+a(depth[y]-depth[x]+1)$	$q_1$ 区间加 $a$ ； $q_2$ 区间加 $a(1-depth[x])$
3 询问 $x$	输出 $A[x]$	$depth[x] \cdot q_1$ 点查 $+\ q_2$ 点查

三类操作全部统一为"区间加、点查"：树状数组按差分实现（左端 $+v$ 、右端后一位 $-v$ ，点查即前缀和），单次 $O(\log n)$ ，朴素做法的 $O(N)$ 瓶颈被彻底消除。查询端的乘法只发生一次——深度 $depth[x]$ 是只读的固定值，不影响更新复杂度。实现上用显式栈做迭代 DFS 求欧拉序，规避 Python 默认递归深度在链状树上的限制。

代码

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#!/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:12
# update_at: 2026-09-30 18:12

import sys


def tour(adj: list[list[int]], root: int) -> tuple[list[int], list[int], list[int]]:
    """迭代 DFS 求欧拉序：返回入点时刻 tin、出点时刻 tout、深度 depth（均为 1 起下标）。

    以入点时刻为编号，子树恰好对应连续区间 [tin[u], tout[u]]。
    """
    n = len(adj) - 1
    tin = [0] * (n + 1)
    tout = [0] * (n + 1)
    depth = [0] * (n + 1)
    t = 0
    stack = [(root, 0, False)]  # (节点, 父节点, 是否为出栈标记)
    while stack:
        u, p, exiting = stack.pop()
        if exiting:
            tout[u] = t  # 此时子树内所有节点都已计完入点时刻
            continue
        t += 1
        tin[u] = t
        depth[u] = depth[p] + 1 if p else 0  # 根深度记 0
        stack.append((u, p, True))
        stack += [(v, u, False) for v in adj[u] if v != p]
    return tin, tout, depth


def bit_add(bit: list[int], i: int, v: int) -> None:
    """树状数组下标 i 加 v。"""
    while i < len(bit):
        bit[i] += v
        i += i & -i


def bit_sum(bit: list[int], i: int) -> int:
    """树状数组前缀和 Σ[1..i]。"""
    s = 0
    while i:
        s += bit[i]
        i -= i & -i
    return s


def range_add(bit: list[int], l: int, r: int, v: int) -> None:
    """区间 [l, r] 每个位置加 v：差分写法，左端 +v、右端后一位 −v，点查即前缀和。"""
    bit_add(bit, l, v)
    bit_add(bit, r + 1, -v)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)
    weight = [0] + [next(data) for _ in range(n)]

    adj: list[list[int]] = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        fr, to = next(data), next(data)
        adj[fr].append(to)
        adj[to].append(fr)
    tin, tout, depth = tour(adj, 1)

    # 设 A[y] = 根到 y 的路径点权和。每次修改对 A[y] 的贡献要么是常数，
    # 要么是 depth[y] 的线性函数，故拆成两棵树状数组：
    # A[y] = depth[y] * q1 点查 + q2 点查（区间加、点查）。
    q1 = [0] * (n + 2)
    q2 = [0] * (n + 2)

    # 初始权值：u 的权值让子树内每个 y 的路径和都 +weight[u]
    for u in range(1, n + 1):
        range_add(q2, tin[u], tout[u], weight[u])

    out: list[str] = []
    for _ in range(m):
        op = next(data)
        x = next(data)
        l, r = tin[x], tout[x]
        if op == 1:  # 单点加 a：只影响子树内 y 的路径和，统一 +a
            a = next(data)
            range_add(q2, l, r, a)
        elif op == 2:  # 子树加 a：y 的路径和 += a * (子树内祖先个数)
            a = next(data)  # y 在子树内时为 a*(depth[y]-depth[x]+1)，否则为 0
            range_add(q1, l, r, a)                      # depth[y] 的系数 a
            range_add(q2, l, r, a * (1 - depth[x]))     # 常数项 a*(1-depth[x])
        else:  # 询问：根到 x 的路径点权和
            out.append(str(depth[x] * bit_sum(q1, tin[x]) + bit_sum(q2, tin[x])))

    print('\n'.join(out))


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/**
 * 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:25
 * update_at: 2026-10-05 08:25
 */
#include <cstdio>
#include <vector>
using namespace std;

typedef long long ll;

// 题目数据规模：N, M <= 1e5
const int MAXN = 100005;

int n, m;

vector<int> g[MAXN]; // 邻接表，g[u] 存与 u 相邻的点（树题用 vector 写法更直观）

ll weight[MAXN]; // weight[u]：节点 u 的初始权值

int tin[MAXN];   // tin[u]：DFS 进入 u 的时刻（欧拉序编号，1 起）
int tout[MAXN];  // tout[u]：u 子树内最后一个点的进入时刻，子树对应 [tin[u], tout[u]]
int depth[MAXN]; // depth[u]：根为 0 的深度，最大不超过 n，用 int 即可
int par[MAXN];   // par[u]：u 的父亲，根的父亲记 0

ll bit1[MAXN]; // 树状数组 1：维护 A[y] 中 depth[y] 的一次项系数
ll bit2[MAXN]; // 树状数组 2：维护 A[y] 中的常数项

int stk[MAXN * 2]; // 迭代 DFS 的显式栈：正数为进入事件，负数为对应节点的退出事件

// 迭代 DFS 求欧拉序与深度：用显式栈代替递归，避免链状树上的爆栈。
// 栈中正数表示进入节点，负数表示该节点子树已全部进入（退出事件）。
void build_tour() {
    int top = 0;
    int timer = 0;
    stk[++top] = 1;
    par[1] = 0;
    depth[1] = 0;
    while (top > 0) {
        int u = stk[top--];
        if (u < 0) {
            tout[-u] = timer; // 退出时，子树内所有点都已编号
            continue;
        }
        tin[u] = ++timer;
        stk[++top] = -u; // 先压退出事件，保证它排在所有孩子之后
        for (size_t i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if (v == par[u]) continue;
            par[v] = u;
            depth[v] = depth[u] + 1;
            stk[++top] = v;
        }
    }
}

// 树状数组单点加：下标 i 处加 v。
void bit_add(ll bit[], int i, ll v) {
    for (; i <= n + 1; i += i & -i) {
        bit[i] += v;
    }
}

// 树状数组前缀和 Σ(1..i)：在差分写法下就是单点查询。
ll bit_sum(ll bit[], int i) {
    ll s = 0;
    for (; i > 0; i -= i & -i) {
        s += bit[i];
    }
    return s;
}

// 区间 [l, r] 统一加 v：差分树状数组，左端 +v、右端后一位 -v。
void range_add(ll bit[], int l, int r, ll v) {
    bit_add(bit, l, v);
    bit_add(bit, r + 1, -v);
}

int main() {
    scanf("%d %d", &n, &m);
    for (int u = 1; u <= n; u++) {
        scanf("%lld", &weight[u]);
    }
    for (int i = 1; i < n; i++) {
        int fr, to;
        scanf("%d %d", &fr, &to);
        g[fr].push_back(to);
        g[to].push_back(fr);
    }
    build_tour();

    // 设 A[y] = 根到 y 的路径点权和。所有修改对 A[y] 的贡献要么是常数，
    // 要么是 depth[y] 的一次函数，因此写成 A[y] = depth[y] * bit1 点查 + bit2 点查。
    // 初始权值：u 的权值让子树内每个 y 的 A[y] 都 +weight[u]，属于常数项。
    for (int u = 1; u <= n; u++) {
        range_add(bit2, tin[u], tout[u], weight[u]);
    }

    for (int i = 1; i <= m; i++) {
        int op, x;
        scanf("%d %d", &op, &x);
        int l = tin[x], r = tout[x];
        if (op == 1) {
            // 单点加 a：只影响子树内每个 y，统一 +a
            ll a;
            scanf("%lld", &a);
            range_add(bit2, l, r, a);
        } else if (op == 2) {
            // 子树加 a：y 在子树内时 A[y] 增加 a*(depth[y]-depth[x]+1)，
            // 拆成 depth[y] 的系数 a 与常数项 a*(1-depth[x]) 两段区间加。
            ll a;
            scanf("%lld", &a);
            range_add(bit1, l, r, a);
            range_add(bit2, l, r, a * (1 - depth[x]));
        } else {
            // 询问根到 x 的路径点权和
            ll ans = depth[x] * bit_sum(bit1, tin[x]) + bit_sum(bit2, tin[x]);
            printf("%lld\n", ans);
        }
    }
    return 0;
}

复杂度

时间：一次迭代 DFS 求欧拉序 $O(n)$ ；每个操作 $O(\log n)$ 次树状数组更新/查询，总计 $O((n + m) \log n)$ ，与 C++ 正解（DFS 序 + 树状数组、或树链剖分 + 线段树）同阶。
空间： $O(n)$ ，邻接表、欧拉序数组与两棵树状数组各 $O(n)$ 。

总结

祖先链与子树是树上一对对偶结构：DFS 序让子树变连续，而"祖先链"通过贡献视角 （点 $u$ 影响整棵子树）被翻译成同一种坐标下的区间操作。
子树加的贡献 $a(depth[y]-depth[x]+1)$ 含有与位置有关的 $depth[y]$ ，用"一次项 + 常数项"拆成两棵树状数组，是把非统一增量化归为统一区间加的常用手法。
最终三类操作全部是"区间加、点查"，差分树状数组 $O(\log n)$ 完成，总复杂度 $O((n+m)\log n)$ ；Python 实现全部 10 组真实数据 0.4s 内通过。

「一本通 4.5 练习 1」树上操作

目录

形式化题目

正解

思路

代码

复杂度

总结