如果查询只是“某棵子树里有多少种颜色”，可以扫描子树，用集合去重。加入“把整棵子树改成同一种颜色”后，反复扫描可能在每次操作都碰到整棵树。

本篇把已有的DFS 序与子树区间和懒标记线段树接起来：先证明子树能变成连续区间，再为“颜色集合”和“覆盖染色”设计彼此相容的摘要与标记。它与莫队算法的区别在于，这里的修改和查询必须按时间顺序生效。

官方题目与输入范围

题目为 Codeforces 620E New Year Tree。官方页面核对日期为 2026-10-05；本文使用原创中文概括与推导。

项目 官方信息
难度与标签 2100；bitmasks、data structures、trees
节点数 n 与操作数 m 均为 1 到 400000
树结构 无向树，根固定为节点 1
初始与修改颜色 编号 1 到 60
操作 1 v c 将 v 的整棵子树，包括 v，覆盖为颜色 c
操作 2 v 查询 v 子树中不同颜色的数量

颜色编号只表示类别，没有加法意义。把颜色 2 覆盖成颜色 5，并不等于给节点加 3；覆盖操作会抹去该范围里原来的所有颜色。

为什么不能只保存颜色数量

左右区间都含两种颜色，它们的并集可能仍为两种，也可能为四种。节点若只保存“不同颜色数”，就不知道两边的重复关系。

左集合 右集合 两边数量 合并数量
{1,2} {1,2} 2 与 2 2
{1,2} {2,3} 2 与 2 3
{1,2} {3,4} 2 与 2 4

本题最多 60 种颜色，可以把整个集合放进一个 64 位整数：颜色 c 对应 1ULL << (c-1)。颜色 1 使用第 0 位，颜色 60 使用第 59 位。

合并使用按位 OR。某颜色只要在任一孩子中出现，对应位就为 1；出现多次仍只占一位。查询结束后再计算置位数，不能将孩子的置位数直接相加。按位 XOR 会把两边都有的颜色消掉，也不是集合并集。

先序 DFS 怎样得到子树区间

维护 tin[v] 为首次访问位置，size[v] 为子树节点数。先序遍历会完整处理一个孩子的所有后代后，才进入下一个孩子，因此 v 的子树恰占闭区间 [tin[v], tin[v]+size[v]-1]。

本文树上遍历使用显式栈：弹出一个节点时记录进入位置，把孩子压入栈。后进先出保证最后压入的孩子及其后代会先被完整处理。孩子访问顺序可以不同，只要每棵子树内部连续，就不影响这里的操作。

得到先序数组后，逆序扫描它，将每个节点的 size 累加给父节点。后代的先序位置总在祖先后面，逆序时后代统计已经完整，因而能计算全部子树大小。树上遍历没有递归，链形树也不会产生四十万层调用栈；线段树的递归深度则只有 O(log n)。

用原创小树演算：1 的孩子为 2、3；2 的孩子为 4、5；3 的孩子为 6。取先序 [1,2,4,5,3,6]：

节点 tin size 子树区间 初始颜色
1 1 6 [1,6] 1
2 2 3 [2,4] 2
4 3 1 [3,3] 2
5 4 1 [4,4] 3
3 5 2 [5,6] 3
6 6 1 [6,6] 60

实现可能得到另一种合法先序；下表只是固定一种顺序便于手算，不是要求代码按节点编号排序孩子。

区间摘要和覆盖标记分别表示什么

每个线段树节点保存两个 64 位数：mask 表示区间内出现过的颜色；lazy 非零时表示整个区间最近被赋值为这个单色位集，孩子还可能保留旧摘要。0 用作“没有待下传赋值”，因为合法颜色的单色位集永远非零。

若一个区间被完整染成 c，不管原来包含多少节点、多少颜色，都有 mask=bit(c)。同时把 lazy 覆盖为 bit(c)。这里不用乘区间长度：摘要表示是否出现，而非出现次数。

原标记 后来的完整覆盖 合成标记 原因
无标记 染成 2 颜色 2 的单色位集 全段同色
染成 2 染成 5 颜色 5 的单色位集 后赋值覆盖前赋值
染成 60 染成 60 颜色 60 的单色位集 重复赋值仍同色

标记组合既不是 OR，也不是累加。染成 2 后 染成 5，集合只剩 {5}，而非 {2,5}。

部分访问之前为什么必须下传

父节点有覆盖标记时，父摘要是最新的，但孩子可能仍描述覆盖前的颜色。下一次操作只访问其中一部分，就必须先将父标记应用到两个孩子，再将父 lazy 设为 0。

之后若执行局部修改，递归更新受影响的孩子，再以左右孩子 mask 的 OR 重算父摘要。查询本身不改颜色，但部分查询也要下传，才能读取真实的子区间集合。完整覆盖的查询直接返回父 mask，不必下传。

手工演算覆盖之后的查询

继续使用上面的六节点树。初始颜色集合为 {1,2,3,60}。

时间顺序 对应区间 最新颜色或查询集合 输出
查询子树 2 [2,4] {2,3} 2
将子树 2 染成 60 [2,4] 节点 2、4、5 均为 60 无
查询整树 [1,6] {1,3,60} 3
将根的子树染成 2 [1,6] 全树为 2 无
单独将节点 4 染成 3 [3,3] 只有节点 4 为 3 无
查询子树 2 [2,4] {2,3} 2
查询子树 3 [5,6] {2} 1

“根覆盖后又改一个叶子”能暴露下传遗漏：如果孩子还拿着旧的颜色 60，后续查询就会把已经不存在的颜色统计回来。

正确性证明

先序连续性已证明每个子树与一个闭区间一一对应，后续只需证明区间操作正确。

构建。 叶子 mask 为节点颜色的单色位集，内部节点 OR 两个孩子。按树高归纳，所有 mask 都恰为各自区间的颜色集合。

覆盖更新。 完整覆盖时全段只有新颜色，单色 mask 与 lazy 正确。部分覆盖前先下传，把父节点此前的赋值落实到孩子，使访问前孩子摘要正确；递归更新相交孩子后，用 OR 恢复父集合。新赋值替换旧标记，符合时间顺序。

查询。 完整包含的区间返回正确集合；部分查询下传后从相交孩子取得集合并做 OR，得到整个目标区间的并集。最终置位数等于颜色种类数，因为颜色与位位置一一对应。

由三者归纳，任意交错的覆盖与查询都得到当前时刻的正确结果。

完整 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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <vector>
using namespace std;
using Mask = unsigned long long;

struct SegmentTree {
    int n;
    vector<Mask> mask, lazy;
    explicit SegmentTree(const vector<Mask>& values)
        : n(static_cast<int>(values.size()) - 1), mask(4 * n), lazy(4 * n, 0) {
        build(1, 1, n, values);
    }
    void build(int p, int l, int r, const vector<Mask>& values) {
        if (l == r) { mask[p] = values[l]; return; }
        int mid = (l + r) / 2;
        build(p * 2, l, mid, values);
        build(p * 2 + 1, mid + 1, r, values);
        pull(p);
    }
    void pull(int p) { mask[p] = mask[p * 2] | mask[p * 2 + 1]; }
    void apply(int p, Mask value) { mask[p] = value; lazy[p] = value; }
    void push(int p) {
        if (lazy[p] == 0) return;
        apply(p * 2, lazy[p]);
        apply(p * 2 + 1, lazy[p]);
        lazy[p] = 0;
    }
    void assign(int p, int l, int r, int ql, int qr, Mask value) {
        if (ql <= l && r <= qr) { apply(p, value); return; }
        push(p);
        int mid = (l + r) / 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);
        pull(p);
    }
    Mask query(int p, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return mask[p];
        push(p);
        int mid = (l + r) / 2;
        Mask result = 0;
        if (ql <= mid) result |= query(p * 2, l, mid, ql, qr);
        if (qr > mid) result |= query(p * 2 + 1, mid + 1, r, ql, qr);
        return result;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> color(n + 1);
    for (int v = 1; v <= n; ++v) cin >> color[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), tin(n + 1), size(n + 1, 1);
    vector<int> stack{1}, order;
    order.reserve(n);
    while (!stack.empty()) {
        int v = stack.back();
        stack.pop_back();
        tin[v] = static_cast<int>(order.size()) + 1;
        order.push_back(v);
        for (int u : graph[v]) {
            if (u == parent[v]) continue;
            parent[u] = v;
            stack.push_back(u);
        }
    }
    for (int i = n - 1; i > 0; --i) {
        int v = order[i];
        size[parent[v]] += size[v];
    }
    vector<Mask> values(n + 1);
    for (int v = 1; v <= n; ++v) values[tin[v]] = 1ULL << (color[v] - 1);
    SegmentTree tree(values);
    while (m--) {
        int type, v;
        cin >> type >> v;
        int l = tin[v], r = l + size[v] - 1;
        if (type == 1) {
            int c;
            cin >> c;
            tree.assign(1, 1, n, l, r, 1ULL << (c - 1));
        } else {
            Mask result = tree.query(1, 1, n, l, r);
            cout << __builtin_popcountll(result) << '\n';
        }
    }
}

__builtin_popcountll 是 Codeforces 常用 GCC 工具链提供的内建函数，不属于 ISO C++17 标准库；使用其他编译器时，可用循环 x &= x-1 逐个清除最低置位来计数。

复杂度与边界清单

DFS、子树大小统计与线段树构建均为 O(n)。每次赋值或查询为 O(log n)，OR 与 64 位置位计数视为常数，因此总时间 O(n+m log n)，空间 O(n)。

边界或错误 检查方法
颜色 60 使用 1ULL，避免 32 位左移
查询单个叶子 颜色数量永远为 1
全树覆盖后修改叶子 必须先下传根的最新覆盖
两个孩子颜色相同 OR 保留一位，不能相加或 XOR
父子子树连续覆盖 后来的赋值覆盖先前标记
根为节点 1 不能把输入中较小编号自动当父节点
链形树 n=400000 树上遍历使用显式栈
闭区间尾端 tin+size-1，不是 tin+size
没有待标记 0 是哨兵，合法颜色位集不能为 0

独立验证应在树上按孩子关系直接重染和集合查询，避免参考程序也使用 DFS 区间与线段树。大规模链与星形树还需要专门检查深度、根覆盖及第 59 位。

怎样推广这组设计

本题能把集合压进单个整数，依赖颜色种类不超过 60。若种类扩大，位集宽度、合并成本和空间都要重新分析。若树的根会改变，某节点子树也不再固定对应同一段区间。

复盘时可以连续回答三句话：为什么一个子树连续，为什么 OR 能代表颜色并集，为什么覆盖标记可以直接替换。把这三个理由拆开，比记住“树上题套线段树”更容易迁移到新问题。