Hellc

Hellc

S国 有 $N$ 个 城市，编号从 $1$ 到 $N$ 。

城市间用 $N - 1$ 条双向道路连接，满足从一个城市出发可以到达其它所有城市。

每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰，为了方便，我们用不同的正整数代表各种宗教。

S国 的居民常常旅行。旅行时他们总会走最短路，并且为了避免麻烦，只在 信仰和他们相同 的城市留宿。当然旅程的终点也是信仰与他相同的城市。

S国政府为每个城市标定了不同的旅行评级，旅行者们常会记下途中（包括起点和终点）留宿过的城市的评级 总和 或 最大值。

在S国的历史上常会发生以下几种事件：

• CC x c ：城市 x 的居民全体改信了 c 教。
• CW x w ：城市 x 的评级调整为 w。
• QS x y ：一位旅行者从城市 x 出发，到城市 y，并记下了途中留宿过的城市的评级总和。
• QM x y ：一位旅行者从城市 x 出发，到城市 y，并记下了途中留宿过的城市的评级最大值。

由于年代久远，旅行者记下的数字已经遗失了，但记录开始之前每座城市的信仰与评级，还有事件记录本身是完好的。

请根据这些信息，还原旅行者记下的数字。

为了方便，我们认为事件之间的间隔足够长，以致在任意一次旅行中，所有城市的评级和信仰保持不变。

Read full article from Hellc