树上启发式合并

例题

给定一棵树，第 \(i\) 个节点颜色为 \(c_i\)。你需要求出对于每个节点 \(u\)，以 \(u\) 为根的子树中出现次数最多的颜色是哪个。

\(n,c_i\le 10^5\)

我们可以用桶数组记录每种颜色出现的次数。但是空间不够给每个点都开一个桶，而转移又需要所有直系子节点的桶。这时就可以考虑使用树上启发式合并。

树上启发式合并只需要开 \(1\) 个全局的桶数组，但需要编写 \(2\) 个 dfs 函数。dfs1(int u) 会统计 \(u\) 子树内的答案；dfs2(int u) 会将 \(u\) 子树内所有颜色出现的次数直接累加在桶数组上，而不更新答案。

我们有一种很暴力的做法：在 dfs1(u) 中循环给每个子树调用 dfs1，更新子树的答案之后，调用 dfs2 得到节点 \(u\) 的桶并更新答案。这种算法的时间复杂度为 \(O(n^2)\)，但可以进一步优化。

注意到节点 \(u\) 在最后一次调用 dfs1(v) 时，可以控制 dfs1(v) 让其保留计算得到的桶，这样就无需调用 dfs2(v) 了。我们可以通过调整使得节点数量最多的子树（重儿子）总在最后调用并保留结果，就可以最小化 dfs2(v) 的计算次数。这种优化看似没有减小时间复杂度，但实际上可以直接将时间复杂度优化至 \(O(n\log n)\)。

我们注意到 dfs1(u) 只会对所有轻边调用 dfs2(v)。这样每个节点被 dfs2 计算到的次数就是返根链中轻边的条数。注意到轻边的条数的上限是 \(log_2n\)，因此总时间复杂度是 \(O(n\log n)\)。

目前没有例题...