题解

思路

把树任意根化，并从叶子向根处理，设要求构造的操作前颜色串为 $T$。

做法

处理非根顶点 $u$ 时，它的孩子颜色已经确定，而孩子数为偶数：若颜色等于 $S_u$ 的孩子超过一半，则父亲取任意颜色都能满足 $u$；若恰好一半，就必须令父亲颜色为 $S_u$；若不足一半则无解。叶子的孩子数为零，因此会直接强制父亲颜色。若某个顶点尚未被孩子强制，非根顶点令其颜色等于父亲的目标颜色不会损失可行性，根则任选一种颜色。

最后在根处检查其所有孩子中是否严格过半等于根的目标颜色，并检查所有强制是否冲突。

复杂度

每条边只被处理常数次，时间复杂度为 $O(N)$，空间复杂度为 $O(N)$。