子树灌满，根路径排空，然后询问一个顶点是否有水。两种修改作用在同一棵树上，却对应不同形状：子树适合 DFS 区间，路径未必连续。重链剖分把路径切成少量区间，同时保留子树连续性，于是可以共用一棵覆盖赋值线段树。

这篇从1006E 子树区间、620E 子树染色进入动态路径更新。与600E 小并大的静态合并不同，343D 必须按输入顺序处理修改，不能计算一次子树袋子后结束。

先修

子树与覆盖标记

会把一次赋值理解为替换旧值，而不是累加或翻转。

核心

一套编号，两种区间

子树只有一段，根路径由若干重链片段组成。

检查

树遍历不使用递归

五十万点链也能构造父子关系、子树大小与重链编号。

子树填满 → 一段赋值 1根路径排空 → 分段赋值 0单点状态 → 查询最后覆盖

官方操作与约束

Codeforces 343D Water Tree 官方题目于 2026-10-10 核对。下面为概括与原创推导，不复制整段题面。

项目 官方信息
难度与标签 2100；data structures、dfs and similar、graphs、trees
顶点 n 与操作 q 各为 1 到 500000
根与初态 根为 1；所有顶点起初为空
1 v v 及其全部后代灌满
2 v v 及其全部祖先排空
3 v 满输出 1，空输出 0
时间与内存 4 秒；256 MB

无向输入保证是一棵树。先输入 n 与 n−1 条边，再输入 q 与操作。祖先、后代操作都包括 v 本身；排空一个顶点不会自动排空它的全部后代。这里是题目指定的离散模拟，不是自行增加物理联动规则。

为什么普通 DFS 区间还不够

朴素修改逐顶点访问，单次可达 O(n)，整串操作最坏 O(nq)。先序 DFS 让子树成为连续段，却不保证任意根路径连续：在访问下一个路径顶点之前，可能已经访问了旁支。

重链剖分选择每个顶点的最大子树孩子为重孩子，其他孩子为轻孩子，沿重边构成重链。选择依据是子树顶点数，不是深度、颜色或编号。大小相等时任选一个即可。

数组 含义
parent[v] 父节点，根的父节点记为 0
size[v] 包含自身的子树大小
heavy[v] 最大子树孩子，没有孩子则为 0
head[v] v 所在重链的链头
pos[v] 重孩子优先遍历给出的序号，从 1 开始

不需要 LCA：本题另一端始终是根。depth 也不是必需数组；每次越过链头就向父节点移动，直到进入根所在链。

重孩子优先编号同时保留两种连续性

先从根构造父先于子的 order，逆序计算 size 与 heavy。随后显式栈存待访问的轻链头；沿当前重链走到底，依次编号，同时把轻孩子压栈。

这里使用 LIFO 栈而不是队列。较深顶点压入的轻子树会先于祖先旁支处理；每个子树处理完，才会转向子树外的待处理项。于是这仍是重孩子优先的 DFS，虽然没有递归调用。

因此一条重链的编号连续且由上到下递增，节点 v 的整棵子树也恰好是 [pos[v], pos[v]+size[v]−1]。计算 size 的 order 可以是父先于子的其他顺序，但最终 pos 不能直接用那个顺序；把两者混为一谈会破坏子树区间。

根路径如何拆成少量片段

从 v 开始。如果 head[v] != head[1]，当前链头到 v 对应 [pos[head[v]],pos[v]]，将这段赋为 0，然后令 v=parent[head[v]]。这一步离开当前重链，越过一条轻边。进入根链后，更新 [pos[1],pos[v]]。

这些片段首尾衔接、不重复也不漏点：每次恰好覆盖当前位置到当前链头的路径，下一次从链头父节点继续。兄弟子树不在这些区间里。

为什么只有 O(log n) 段？若 p 的轻孩子 v 有大小 s，p 的重孩子大小至少也是 s，故 size[p] >= 1+2s。沿轻边向下时子树大小至少减半，根路径上只能遇到 O(log n) 条轻边。重边再长也不增加片段数。

覆盖线段树只需要三个标记状态

节点标记为 0 或 1，表示整段已知统一状态；为 −1，表示需要继续看孩子。初始整棵树全为 0，因此所有数组位置初始化为 0 即可。

完整覆盖一个线段树节点时直接写入新标记。部分覆盖时，如果父标记仍为 0 或 1，先把这个状态赋给两个孩子，再把父标记改为 −1，继续进入相交的孩子。单点查询遇到统一标记即可返回。

这份程序不维护区间和，更新后也不需要 pull。父标记为 −1 时即使两个孩子碰巧相同，查询继续向下仍然正确；只是没有额外做压缩优化。

标记组合 应采用的规则
先填满，后排空 最终为 0
先排空，后填满 最终为 1
重复填满 仍为 1，不翻转
旧统一标记后局部修改 先下传旧状态，再修改局部

与242E 异或标记相比较，赋值是后者替换前者，不是 lazy ^= value。一次较新的整段覆盖也会遮住更旧的孩子状态；以后再局部更新时才通过下传同步。

手工编号与交错修改

树边为 1−2、1−3、2−4、2−5、3−6、6−7。相同大小时本例选 2、4 为重孩子，可得到：

顶点 1 2 4 5 3 6 7
pos 1 2 3 4 5 6 7
head 1 1 1 5 3 3 3

子树 2 对应 [2,4]；根到 7 则拆成 [5,7] 与 [1,1]。区间是 pos，不是原顶点编号。

操作 按顶点编号 1 到 7 的水状态
初始 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1
2 7 0 1 0 1 1 0 0
1 3 0 1 1 1 1 1 1
2 5 0 0 1 1 0 1 1

最后顶点 4 仍为 1：排空 5 只影响 5、2、1，不影响兄弟 4。这个例子可检查“祖先”误写成“子树”的方向错误。

正确性与复杂度

重孩子优先编号保证子树段与重链段准确；路径分段每次覆盖当前链内的那一截，再继续父链，因此恰好覆盖根路径。线段树的统一标记和下传保持每个叶子的最新赋值。对操作序列归纳：初态一致，两类修改恰好替换目标顶点集合，查询读到当前状态，所以每次输出正确。

建图、两次树遍历与编号 O(n)。子树修改和单点查询各 O(log n)，根路径修改 O(log² n)，总时间 O(n+q log² n)，额外空间 O(n)。树遍历无递归；线段树递归深度仍为 O(log n)，五十万点链不使它变深。

完整 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
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

struct AssignTree {
    int n;
    vector<int> tag;
    explicit AssignTree(int count) : n(count), tag(4 * count + 4, 0) {}
    void assign(int p, int l, int r, int ql, int qr, int value) {
        if (ql <= l && r <= qr) { tag[p] = value; return; }
        if (tag[p] != -1) {
            tag[p * 2] = tag[p * 2 + 1] = tag[p];
            tag[p] = -1;
        }
        int mid = l + (r - l) / 2;
        if (ql <= mid) assign(p * 2, l, mid, ql, qr, value);
        if (qr > mid) assign(p * 2 + 1, mid + 1, r, ql, qr, value);
    }
    void assign(int l, int r, int value) { assign(1, 1, n, l, r, value); }
    int get(int p, int l, int r, int at) const {
        if (tag[p] != -1) return tag[p];
        int mid = l + (r - l) / 2;
        if (at <= mid) return get(p * 2, l, mid, at);
        return get(p * 2 + 1, mid + 1, r, at);
    }
    int get(int at) const { return get(1, 1, n, at); }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    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), size(n + 1, 1), heavy(n + 1), order{1};
    for (size_t i = 0; i < order.size(); ++i) {
        int u = order[i];
        for (int v : graph[u]) if (v != parent[u]) {
            parent[v] = u; order.push_back(v);
        }
    }
    for (int i = n - 1; i >= 0; --i) {
        int u = order[i];
        for (int v : graph[u]) if (parent[v] == u) {
            size[u] += size[v];
            if (heavy[u] == 0 || size[v] > size[heavy[u]]) heavy[u] = v;
        }
    }
    vector<int> head(n + 1), pos(n + 1);
    vector<pair<int, int>> pending{{1, 1}};
    int timer = 0;
    while (!pending.empty()) {
        auto chain = pending.back(); pending.pop_back();
        for (int u = chain.first; u != 0; u = heavy[u]) {
            head[u] = chain.second; pos[u] = ++timer;
            for (int v : graph[u]) {
                if (parent[v] == u && v != heavy[u]) pending.emplace_back(v, v);
            }
        }
    }
    AssignTree tree(n);
    int q; cin >> q;
    while (q--) {
        int type, v; cin >> type >> v;
        if (type == 1) tree.assign(pos[v], pos[v] + size[v] - 1, 1);
        else if (type == 2) {
            while (head[v] != head[1]) {
                tree.assign(pos[head[v]], pos[v], 0);
                v = parent[head[v]];
            }
            tree.assign(pos[1], pos[v], 0);
        } else cout << tree.get(pos[v]) << '\n';
    }
    return 0;
}

边界与复盘

边界 检查项
n=1、更新根 路径与子树均包含根自身
链与星形 不依赖递归树栈，也不依赖原编号顺序
子树端点 右端点为 pos+size−1，不能多一个
重复同类修改 赋值保持状态，不是翻转
子树填满后路径排空 只改变路径，旁支仍保留水
路径排空后子树填满 后来的赋值覆盖旧状态，时间顺序不能重排

tests/verify-water-tree-article.cjs 提取本文代码编译，以逐顶点灌水和逐父节点排水独立对拍，覆盖小树操作组合、随机编号、五十万点链与最大操作数。对拍验证实现，重链分段与连续性的证明解释为什么方法成立。

进一步想：如果要维护两点路径的和呢？

需要比较链头深度，先处理更深的一侧，并在最后处理同链区间；线段树也要增加长度、区间和与 pull。先补齐新的查询摘要，不要直接把本题只有单点查询的标记树搬过去。