每个顶点都要回答：自己的子树里，哪些颜色出现得最多？把这些颜色的编号相加。对子树反复遍历会做许多重复工作，但直接把孩子的答案相加也不对；真正需要复用的是颜色频次。

这篇接在树上 DFS、子树区间与子树染色之后。620E 有在线修改，600E 的树和颜色完全静态，因此可以自底向上合并袋子；我们选择迭代遍历，避免十万点长链带来的递归栈风险。

阅读前

会划分父子关系

子树互不重叠，父节点的统计由自己的颜色与各孩子的统计组成。

关键问题

频次不能丢

众数答案不是可直接相加的摘要；小袋里的计数必须进入大袋。

完成标志

说清谁在翻倍

被收费的是源子树中的顶点，而不是可能发生碰撞的颜色键。

官方题目与范围

题目为 Codeforces 600E Lomsat gelral，以下信息于 2026-10-09 按官方题目页核对。题意只做概括，下面的推导、例子和代码为本站原创。

项目 官方信息
难度 2300
标签 data structures、dfs and similar、dsu、trees
顶点数 n 1 到 100000
颜色编号 1 到 n
结构 n−1 条无向边构成树，根为 1
输出 按顶点编号输出每棵子树的所有最高频颜色编号之和
限制 2 秒；256 MB

并列最高频的颜色全部计入，每个颜色编号只加一次，不乘出现次数。答案可能超过 32 位：当所有颜色 1 到 100000 各出现一次，根的答案为 100000×100001/2 = 5000050000。频次可以用 int，答案使用 long long。

只保存孩子的众数会漏掉什么

朴素做法对每个顶点重新扫描整棵子树。长链的工作量为 n+(n−1)+…+1，最坏 O(n²)。

但把每个孩子的“最高频次与众数和”当作节点摘要也不够。设 n 至少为 7，父节点自己的颜色为 7：

子树 各颜色频次 子树的最高频颜色
孩子 A 1 出现 3 次；3 出现 2 次 1
孩子 B 2 出现 3 次；3 出现 2 次 2
合并 A、B 和父节点 1：3；2：3；3：4；7：1 3

颜色 3 在两个孩子里都不是众数，在父节点却成为唯一众数。仅保留两个孩子的答案会永久丢失它的频次。与区间异或的固定 20 位摘要不同，这里保留一个 颜色 → 次数 的完整映射。

袋子保存什么，怎样增量维护答案

每个当前袋子维护三个量：freq[c] 为颜色 c 的次数；best 为最高频次；sum 为达到 best 的所有颜色编号之和。空袋 best=0, sum=0。

把颜色 c 的次数增加 delta，设更新后的频次为 k。其他颜色没有变化：

k 与旧 best 的关系 新 best 新 sum
k 小于 best 不变 不变
k 等于 best 不变 加上 c
k 大于 best 改为 k 重置为 c

delta 必须为正。第二行不会重复加入同一颜色：次数严格增加，更新前它还没有达到这个最高频次。若它原先就处于最高频次，增加后必然进入第三行。

合并整个孩子时，对孩子袋中的每个 (c,count) 调用一次增量更新，不是只增加 1。不能把两个袋子的 best 取最大、sum 相加，因为相同颜色在两边的频次会叠加。

先接管最大子树，再合并其余袋子

这里的“大”按袋子代表的顶点数衡量，具体就是孩子的子树大小，不是 map.size()。即使一棵大子树只有一种颜色，仍然可以直接接管它的袋子。

  1. 先得到每个孩子的袋子与答案。
  2. 找子树顶点数最多的孩子，移动其袋子的所有权给父节点，不复制映射。
  3. 加入父节点自己的颜色一次。
  4. 遍历其余孩子的颜色频次，合并到当前袋子；释放这些已被吸收的袋子。
  5. 保存当前 sum 为父节点答案。以后袋子可能继续变化，但这个数值快照不变。

本实现属于 small-to-large 容器合并。官方标签里的 dsu 不意味着一定要写 find/unite；它也不等同于另一种“保留重子树、清空轻子树贡献”的 sack 写法。两种方法都复用树上统计，但代码与复杂度证明应分别说明。

为什么重复合并总量可控

设一个轻孩子的子树有 s 个顶点。合并它时，目标袋子至少含有最大孩子的全部顶点，最大孩子大小不小于 s，因此合并后的袋子至少代表 2s 个顶点。

一次遍历源袋的条目数不超过 s：不同颜色数不会超过它代表的顶点数。我们把这次遍历的成本上界收费到源子树的 s 个顶点，每个顶点收取常数费用。某个顶点再次作为源袋被收费时，所在袋子质量已至少翻倍；从 1 增长到 n，它至多被收费 O(log n) 次。因此总遍历条目数为 O(n log n)。

这份证明不声称“每个颜色键迁移后，不同颜色数一定翻倍”。相同颜色会碰撞，例如两个大小为 100 的单色子树合并后仍只有一个键。翻倍的是代表的顶点数；按源顶点收费正好绕开键碰撞问题。父节点自己的一次插入，另计 n 次。

代码使用 std::map，单次颜色查找与更新 O(log n)，所以总时间 **O(n log² n)**，不是 O(n log n)。unordered_map 的查找有期望界而非同样的确定性最坏界，本文不据此改写复杂度。

活跃袋子代表的顶点集合互不重叠。合并期间源映射与目标中的新条目短暂并存，总条目仍为 O(n)；合并后立即释放源袋。邻接表、遍历顺序、大小和答案数组也为 O(n)，总额外空间 O(n)。

手工合并一次并列众数

树边为 1−2、1−3、2−4、2−5，颜色依次为 [2,1,3,3,1]。子树 2 有三个顶点，是根的最大孩子；它的袋子为 {1:2,3:1}，best 为 2，sum 为 1。

处理动作 当前频次 best sum
根接管子树 2 1：2；3：1 2 1
加入根的颜色 2 1：2；2：1；3：1 2 1
并入子树 3 的颜色 3 一次 1：2；2：1；3：2 2 4

最终按顶点编号输出 4 1 3 3 1。子树 2 的答案仍是 1，尽管它原来的袋子已经被根接管并修改。把所有节点的答案存成指向袋子的引用会破坏这个快照。

正确性：频次、最高频与遍历顺序

对处理顺序归纳。叶子的空袋加入自身颜色后，频次和答案显然正确。假设一个节点的所有孩子袋子均正确；每个孩子的顶点集合互不重叠，也不含父节点。接管一个孩子、加入父节点、并入其余孩子，恰好把父子树的所有顶点计入一次，所以最终每种颜色的频次正确。

每次增量只改变一种颜色；上述三种比较分别覆盖全部可能，并正确维护最高频次与众数和。因此合并完成时 sum 就是目标答案。

代码先从根构造父节点早于孩子的 order。逆序处理保证每个孩子已经完成；这里不依赖孩子之间的顺序，也不要求 order 是先序 DFS。所有权移动只改变数据存放位置，不改变孩子已经保存的答案。于是每个顶点的输出正确。

完整 C++17 实现

使用显式顺序替代递归，链形树也不会增加调用栈深度。unique_ptr 的 move 是袋子所有权转移，reset 释放的是内存，不涉及任何文件操作。

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

struct Bag {
    map<int, int> freq;
    int best = 0;
    long long sum = 0;

    void add(int color, int delta) {
        int now = (freq[color] += delta);
        if (now > best) {
            best = now;
            sum = color;
        } else if (now == best) {
            sum += color;
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<int> color(n + 1);
    for (int i = 1; i <= n; ++i) cin >> color[i];
    vector<vector<int>> graph(n + 1);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    vector<int> parent(n + 1, 0), order{1};
    parent[1] = -1;
    for (size_t i = 0; i < order.size(); ++i) {
        int u = order[i];
        for (int v : graph[u]) {
            if (v == parent[u]) continue;
            parent[v] = u;
            order.push_back(v);
        }
    }
    vector<int> size(n + 1, 1);
    vector<long long> answer(n + 1);
    vector<unique_ptr<Bag>> bags(n + 1);
    for (int i = n - 1; i >= 0; --i) {
        int u = order[i], heavy = 0;
        for (int v : graph[u]) {
            if (parent[v] != u) continue;
            size[u] += size[v];
            if (heavy == 0 || size[v] > size[heavy]) heavy = v;
        }
        if (heavy != 0) bags[u] = move(bags[heavy]);
        else bags[u] = make_unique<Bag>();
        bags[u]->add(color[u], 1);
        for (int v : graph[u]) {
            if (parent[v] != u || v == heavy) continue;
            for (const auto &entry : bags[v]->freq) {
                bags[u]->add(entry.first, entry.second);
            }
            bags[v].reset();
        }
        answer[u] = bags[u]->sum;
    }
    for (int u = 1; u <= n; ++u) {
        if (u > 1) cout << ' ';
        cout << answer[u];
    }
    cout << '\n';
    return 0;
}

边界与错误清单

情况 需要检查
n=1 没有边，答案为唯一颜色编号
全部同色 众数和为该编号，不是编号乘子树大小
全部不同色 所有颜色并列；根答案可能超过 int
新颜色超过旧最高频 sum 必须重置，不能保留旧众数
大小相同的孩子 任意选择一个接管，不影响答案与翻倍下界
长链 不使用递归树遍历；不要复制最大孩子的 map
保存历史答案 存数值快照，不能随着袋子复用继续改变
静态限制被改变 若加入改色操作，本解不能原样在线维护所有祖先

验证脚本位于 tests/verify-subtree-modes-article.cjs：提取本文唯一 C++17 程序，无警告编译，使用独立的逐子树遍历计数核验小树，并测试十万点链、星形树和颜色碰撞。压力测试通过不等于承诺所有评测机器的墙钟时间；复杂度仍按上面的确定性界解释。

复盘：如果只想知道不同颜色数量呢？

完整频次仍可合并，但摘要的增量规则可以简化。先确定查询需要的信息，再区分接管成本、轻袋遍历成本和字典查找成本；不要看到“小并大”就直接写 O(n log n)。

继续比较620E 在线子树染色和86D 离线窗口频次：三题都统计颜色或数值，复用单位却分别是子树袋子、区间摘要和可移动窗口。