给一个顶点加上一个数，它的孩子减去这个数，孙子再加回来。直接模拟这条传播链并不困难，困难的是让二十万次操作都不再遍历整棵子树。

383C 的关键不是找到更复杂的树结构，而是先换一个数值坐标：奇数深度乘以 −1，偶数深度乘以 +1。原来交替正负的修改，在这个坐标里变成了整棵子树的同号修改。 接上 1006E 子树区间与树状数组计数，只需一棵差分树状数组。

先修

子树是一段 DFS 序

理解进入时间与包含自身的闭区间。

核心

先消除符号交替

更新端与查询端各乘一次深度符号。

检查

用逐边传播对拍

独立模拟每经过一条父子边就变号。

隔层变号 → 深度符号子树 → DFS 闭区间区间加与单点查 → 差分树状数组

官方操作与约束

题目为 Codeforces 383C Propagating tree。以下是操作概括，完整输入约定见官方页面；难度与标签也可在官方题库 API查询。

项目 官方信息
难度与标签 2000；data structures、dfs and similar、trees
顶点 n 与操作 m 均为 1 到 200000
初始值 a 与更新量 val 均为 1 到 1000
根 顶点 1
1 x val x 加 val，向下每经过一条边，增量变号
2 x 输出 x 当前的数值
时间与内存 2 秒；256 MB

更新只向后代传播，包括 x 自身，不会传播到父节点或兄弟。初始值为正，不意味着答案始终为正；奇数距离的后代可能被减到零以下。所有操作按输入顺序执行，不能把查询挪到修改前后。

为什么逐点传播会超时

朴素方法从 x 开始遍历子树，沿每条边反转增量。一次根更新访问 n 个顶点，反复根更新最坏需要 O(nm) 时间。

DFS 序解决了“更新范围是什么”，却还没解决“区间里的每个位置应该加还是减”。深度奇偶在先序数组里不一定交替：先访问完一个孩子的整个分支，再进入下一个孩子，数组相邻位置可能同奇偶。因此不能按 DFS 序下标的奇偶性选择符号。

深度符号为什么能统一更新

设根深度为 0，定义 s(v)：偶数深度取 +1，奇数深度取 −1。对 x 的后代 v，路径长度是 depth[v] − depth[x]，本次增量可以写成：

1
2
3
真实增量 Δ(v) = s(v) × s(x) × val
变换后的累计增量 b(v) = s(v) × (当前值(v) − a[v])
所以本次 b(v) 的变化 = s(v) × Δ(v) = s(x) × val

最后一步用了 s(v) × s(v) = 1。对整个 x 子树，s(x) × val 是同一个数，与 v 的深度无关。

于是更新只做一件事：把统一增量 s(x) × val 加到子树区间。查询则恢复原坐标：

1
当前值(v) = a[v] + s(v) × b(v)

初始数组不必放进树状数组，因为 b 只累计后续修改。这样树状数组初始全零，查询单独加回 a[v]。也可以维护符号变换后的完整数值，但不能把两种初始化方式混在一起。

手工演算更新端与查询端

用一棵六顶点的小树：根 1 的孩子为 2、3；2 的孩子为 4、5；3 的孩子为 6。按这个孩子顺序做 DFS，先序为 [1,2,4,5,3,6]。

顶点 深度 s(v) tin tout 初始值
1 0 +1 1 6 10
2 1 −1 2 4 20
3 1 −1 5 6 30
4 2 +1 3 3 40
5 2 +1 4 4 50
6 2 +1 6 6 60

执行 1 2 7 时，变换后的区间 [2,4] 统一加 −7。查询顶点 2 得到 20 + (−1)×(−7) = 27；查询顶点 4 得到 40 + (+1)×(−7) = 33。同一棵树状数组给出相同的累计量，查询端的符号负责恢复不同的真实增量。

六点树更新顶点2加7时，顶点2实际加7，顶点4和5减7；在DFS序的第二到第四位统一记录负7
真实修改不同，变换后的修改相同。 原创图对应上表，蓝色框选子树2；底行显示 b 的增量，不是实际顶点值，也不是按数组位置决定奇偶。查看原图

再执行根更新与叶子更新，逐点结果如下。每一列始终按顶点编号排列，而不是 DFS 顺序。

已执行的操作 1 2 3 4 5 6
初始 10 20 30 40 50 60
1 2 7 10 27 30 33 43 60
再执行 1 1 3 13 24 27 36 46 63
再执行 1 5 4 13 24 27 36 50 63

第三次更新的 x 深度为偶数，因此变换坐标里加 +4。观察顶点 6：它不属于子树 2，也不属于子树 5，只有根更新影响它。范围与符号必须分别正确。

DFS 闭区间与差分树状数组

进入顶点 v 时记 tin[v]=++timer；它的全部后代处理完后，记 tout[v]=timer。进入时间不重复计数，退出时也不新增序号。于是子树恰好对应闭区间 [tin[v],tout[v]]，叶子满足 tin=tout。

迭代 DFS 用“进入事件”和“退出事件”代替递归调用栈：先放入退出事件，再倒序放入孩子的进入事件。栈后进先出，确保孩子全部处理完才退出当前顶点。倒序只是为了让孩子按邻接表正序访问；本题并不要求固定孩子顺序。

数组或对象 含义
parent[v] 根为 0 的父节点，用来跳过无向边的反向访问
sign[v] 根取 +1，孩子取父节点符号的相反数
tin[v]、tout[v] 从 1 开始的子树闭区间
a[v] 原始数值，始终不修改
Fenwick 变换后累计增量 b 的差分数组

对 b 的数组区间 [l,r] 加 d，只需在差分数组的 l 加 d、r+1 减 d。对位置 p 求差分前缀和，正好得到 b[p]。

本题不是区间和查询，所以一棵树状数组就够了；不需要两棵 BIT 的加权前缀公式，也不需要维护区间总和的线段树。代码仅存下标 1 到 n；r=n 时不写 n+1，它不会参与任何合法位置的前缀查询。

正确性证明

子树连续性。 DFS 进入 v 后，只有完成全部孩子的子树才执行 v 的退出事件。期间获得进入编号的顶点恰好是 v 及其后代，因此 [tin[v],tout[v]] 不包含子树外顶点，也不漏掉任何子树内顶点。

单次更新等价性。 对后代 u，真实增量是 s(u)s(v)val，乘以 s(u) 后变成统一的 s(v)val。对子树外顶点两种表示都不修改。故一次区间加与一次题目传播操作，在变换坐标里完全等价。

差分还原性。 一次更新在 l 留下 +d，在 r+1 留下 −d。p<l 时前缀未包含任何端点；l≤p≤r 时只包含 +d；p>r 时两项抵消。多次更新按加法叠加，因此前缀查询得到所有已执行更新的 b 值。

初始 b 为零，与初始数值一致。上述等价性保证每次修改保持这一关系；查询用 a[u]+s(u)b(u) 逆变换，因 s(u) 的平方为 1，恢复值正是题目要求的当前数值。归纳可知全部操作正确。

边界与错误清单

容易写错的地方 正确做法与反例
用 tin 的奇偶代替深度奇偶 例中顶点3的 tin=5，却与 tin=2 的顶点2同为奇数深度
更新乘了 s(x)，查询忘记乘 s(v) 1 2 7 后顶点2不是 20−7，而是 20+7
初始值重复计入 BIT 与 a 本实现只在 BIT 里保存修改增量
写成半开区间，却仍在 tout+1 抵消 统一使用包含自身的闭区间
叶子没有退出事件 叶子的 tout 必须等于自己的 tin
根更新遗漏最后一个位置 r=n 时跳过右端抵消，不是跳过整次修改
按编号猜测父子关系 输入是无向树，父节点由根为1的遍历决定
默认所有答案为正 减法传播允许合法的负答案
对二十万点链递归 DFS 显式事件栈，空间由容器承担

官方范围内，单点累计增量绝对值不超过 m×1000，32 位有符号整数可以覆盖当前数值范围。实现仍选 long long，让数值类型保持明确，并为复用到更大更新量的练习留余地；不能据此把官方 val 上限说成 10^9。

完整 C++17 实现

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
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

struct Fenwick {
    int n;
    vector<ll> bit;
    explicit Fenwick(int size) : n(size), bit(size + 1, 0) {}
    void add(int p, ll delta) {
        for (; p <= n; p += p & -p) bit[p] += delta;
    }
    ll prefix(int p) const {
        ll result = 0;
        for (; p > 0; p -= p & -p) result += bit[p];
        return result;
    }
    void rangeAdd(int l, int r, ll delta) {
        add(l, delta);
        if (r < n) add(r + 1, -delta);
    }
};

struct Event {
    int vertex;
    bool leaving;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<ll> a(n + 1);
    for (int v = 1; v <= n; ++v) cin >> a[v];
    vector<vector<int>> graph(n + 1);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    vector<int> parent(n + 1, 0), sign(n + 1, 1);
    vector<int> tin(n + 1), tout(n + 1);
    vector<Event> stack;
    stack.reserve(2 * n);
    stack.push_back({1, false});
    int timer = 0;
    while (!stack.empty()) {
        Event event = stack.back();
        stack.pop_back();
        int v = event.vertex;
        if (event.leaving) {
            tout[v] = timer;
            continue;
        }
        tin[v] = ++timer;
        stack.push_back({v, true});
        for (auto it = graph[v].rbegin(); it != graph[v].rend(); ++it) {
            int u = *it;
            if (u == parent[v]) continue;
            parent[u] = v;
            sign[u] = -sign[v];
            stack.push_back({u, false});
        }
    }

    Fenwick fenwick(n);
    while (m--) {
        int type, x;
        cin >> type >> x;
        if (type == 1) {
            ll val;
            cin >> val;
            fenwick.rangeAdd(tin[x], tout[x], sign[x] * val);
        } else {
            cout << a[x] + sign[x] * fenwick.prefix(tin[x]) << '\n';
        }
    }
}

复杂度与适用范围

读边与迭代 DFS 都为 O(n)，每次修改至多两次 BIT 更新，查询一次前缀和。因此总时间 O(n+m log n)，空间 O(n)。显式事件栈在星形或长链树上最多 O(n) 个待处理事件。

变化后的问题 这套方法是否直接适用
固定树上的子树更新与单点查询 可以，正是当前模型
任意两点路径上的隔层修改 不能只用一个子树区间，需要额外路径分解
更新后查询整棵子树的真实值总和 当前单棵差分 BIT 不够，需要维护相应的带符号区间统计
在线换根或改变边 当前 tin、tout 与固定深度符号不能直接照搬
每条边乘的因子不再是 −1 重新检查因子是否能分离为更新端与查询端两部分

继续比较 620E 子树染色与 343D Water Tree：它们改变的是颜色或覆盖状态，不能把不同的标记合成方式混成“都是懒标记”。383C 先通过代数变换统一增量，再用差分解决当前需要的查询；数据结构是在状态定义之后选择的。