CodeForces分析树上启发式合并板子题。维护一个 $cnt_i$ 表示第 $i$ 种颜色的出现次数，$num_i$ 表示有多少种颜色出现 $i$ 次，$sum_i$ 表示所有颜色出现 $i$ 次的节点的编号和。这样子计算贡献显然是 $O(1)$ 的。那么在树上 DFS，重复以下过程：递归处理所有轻儿子，并消去贡献。递归处理重儿子，并保留贡献。将轻儿子的信息合并到重儿子保留的贡献中。若当...
CodeForcesLuogu分析吐槽一下这题目名字怎么这么长...显然，如果只有至多一个字符出现次数为奇数，那么这条路径就是符合要求的。字符只有 $22$ 种，可以状压一下，那么只要异或和有至多一个二进制位为 $1$ 就是合法的。设 $f[i]$ 表示到根路径异或和为 $i$ 的点中最大深度值。然后上 $\mathrm{dsu\ on\ tree}$ 就好了。具体实现及细节见代码。代码//...