9233

P9233 [蓝桥杯 2023 省 A] 颜色平衡树 （dfs序 莫队） 莫队原理:https://zhuanlan.zhihu.com/p/115243708 对于树上的每个结点，按照 dfs 序打上时间戳，这样就可以把每一个结点对应的子树的答案转化为一个区间的答案。将子树询问离线下来变成 \(n ......

看到树上数颜色，想到树上启发式合并（dsu on tree）。 这题几乎就是树上启发式合并板子了，感觉讲一下算法的原理比较好。 暴力解法显然是对每棵子树 dfs 一遍，求出子树大小 $\operatorname{size}$、子树颜色出现次数的桶 $\operatorname{cnt}$，以及颜色出 ......