题目描述

S 国有 $N$ 个城市，编号从 $1$ 到 $N$。城市间用 $N-1$ 条双向道路连接，构成一棵树。

每个城市有两个属性：

• 评级 $W_i$（正整数）
• 信仰（宗教）$C_i$（正整数，$1 \le C_i \le C$，$C$ 为宗教总数）

现在有 $Q$ 个事件，分为四种：

1. CC x c：城市 $x$ 的居民全体改信了宗教 $c$；
2. CW x w：城市 $x$ 的评级调整为 $w$；
3. QS x y：一位旅行者从城市 $x$ 出发，到城市 $y$，他只访问与起点信仰相同的城市，并记下途中留宿过的城市的评级总和（包括起点和终点，且路径上只统计与起点信仰相同的城市）；
4. QM x y：与 QS 类似，但记下的是评级最大值。

保证对于每个 QS 和 QM 事件，起点 $x$ 和终点 $y$ 的信仰相同（因此路径上至少有两个城市信仰相同）。

你需要根据事件记录，回答所有 QS 和 QM 询问。

输入格式

输入的第一行包含整数 $N, Q$ 依次表示城市数和事件数。

接下来 $N$ 行，第 $i+1$ 行两个整数 $W_i, C_i$ 依次表示记录开始之前，城市 $i$ 的评级和信仰。

接下来 $N-1$ 行每行两个整数 $x, y$ 表示一条双向道路。

接下来 $Q$ 行，每行一个操作，格式如上所述。

输出格式

对每个 QS 和 QM 事件，输出一行，表示旅行者记下的数字。

样例

输入样例 1

5 6
3 1
2 3
1 2
3 3
5 1
1 2
1 3
3 4
3 5
QS 1 5
CC 3 1
QS 1 5
CW 3 3
QS 1 5
QM 2 4

输出样例 1

8
9
11
3

样例解释

初始状态： 城市1: (评级3, 信仰1) 城市2: (2,3) 城市3: (1,2) 城市4: (3,3) 城市5: (5,1)

树结构：

    1
   / \
  2   3
     / \
    4   5

1. QS 1 5：从城市1到城市5，只考虑信仰为1的城市。路径为1-3-5，信仰为1的城市有1和5（评级3和5），评级总和=3+5=8。
2. CC 3 1：城市3的信仰改为1。
3. QS 1 5：路径1-3-5，现在城市1、3、5信仰都是1，评级3,1,5，总和=3+1+5=9。
4. CW 3 3：城市3的评级改为3。
5. QS 1 5：路径1-3-5，评级3,3,5，总和=3+3+5=11。
6. QM 2 4：从城市2到城市4，只考虑信仰为3的城市。路径2-1-3-4，信仰为3的城市有2和4（评级2和3），最大值=3。

数据范围

• $N, Q \le 10^5$
• $C \le 10^5$
• 对所有 QS 和 QM 事件，起点和终点城市的信仰相同；
• 在任意时刻，城市的评级总是不大于 $10^4$ 的正整数，且宗教值不大于 $C$。

时间限制：1000 ms
内存限制：262144 KB

提示

因为只统计特定信仰的城市，所以需要按信仰建立多棵线段树，即每个信仰维护一棵线段树，但动态开点避免空间爆炸。

基本思路：

1. 对原树进行树链剖分，得到每个城市的 DFS 序 $dfn[x]$ 和子树区间。
2. 对于每种信仰 $c$，建立一棵线段树（动态开点），维护该信仰的城市的评级信息（区间和、区间最大值）。初始时，将每个城市插入其信仰对应的线段树中。
3. 对于操作：
   • CC x c：将城市 $x$ 从原信仰的线段树中删除（将该位置评级设为0），然后加入新信仰 $c$ 的线段树（将该位置设为 $W_x$）。
   • CW x w：在城市 $x$ 当前信仰的线段树中，将 $x$ 对应的位置评级更新为 $w$，并更新 $W_x = w$。
   • QS x y 和 QM x y：确定起点信仰 $c$（即 $C_x$），然后在信仰 $c$ 的线段树上，查询 $x$ 到 $y$ 路径上所有信仰为 $c$ 的城市的评级和或最大值。因为线段树中只存储信仰为 $c$ 的城市，其他城市评级为0，所以直接查询路径区间即可。

注意：

• 树链剖分后，路径查询需要跳链，每次查询一条链在对应信仰线段树上的区间信息（和或最大值），然后合并。
• 动态开点线段树每个节点维护左右儿子指针、区间和、区间最大值。
• 由于 $C \le 10^5$，每个城市只会出现在一种信仰的线段树中，所以总节点数 $O((N+Q) \log N)$，内存可以承受。

时间复杂度：每个操作 $O(\log^2 N)$，对于 $10^5$ 可以接受。