说明

考虑一棵树，每个顶点上放置了一颗绿色或蓝色的石头。如果在执行以下操作 1 和 2 后能够满足条件 3，则称这样的树为“双子树”。

1. 首先，进行“选择由边直接连接的顶点对，并交换放置在每个端点上的石头”这一操作，可以进行零次或多次。
2. 其次，选择至多一条边并将其删除。
3. 此时，树被分割成至多两个连通分量，并且每个分量中只放置了一种颜色的石头。

考虑一棵每条边都有指定长度的“双子树”，并按如下方式定义其价值。

1. 首先，进行“选择由边直接连接的顶点对，并交换放置在每个端点上的石头”这一操作，可以进行零次或多次。每次交换操作的成本等于该边的长度。
2. 其次，选择至多一条边并将其删除。
3. 此时，树被分割成至多两个连通分量，并且每个分量中只放置了一种颜色的石头。
4. 为达成条件 3 所需的操作 1 的总成本的最小值，即为该“双子树”的价值。

注意，在计算价值时，石头本身不被移动。

你被给定一棵每条边都有指定长度的“双子树”。它有 $N$ 个顶点，其中 $N$ 是奇数。第 $i$ 条边连接两个顶点 $u_i$ 和 $v_i$，长度为 $w_i$。放置在顶点上的石头颜色由字符串 $S = s_1s_2 \ldots s_N$ 表示。

你将对这棵树依次执行 $Q$ 次操作。第 $j$ 次操作由两个整数 $e_j, a_j$ 定义，表示将第 $e_j$ 条边的长度增加 $a_j$。该操作的效果在后续操作中依然保持。请回答每次操作后树的价值。

输入格式

$$\begin{aligned} & N \\ & s_1s_2 \ldots s_N \\ & u_1 \ v_1 \ w_1 \\ & \vdots \\ & u_{N-1} \ v_{N-1} \ w_{N-1} \\ & Q \\ & e_1 \ a_1 \\ & \vdots \\ & e_Q \ a_Q \end{aligned}$$

输入满足以下约束：

• 所有输入均为整数。
• $3 \leq N \leq 10^5$
• $N$ 是奇数。
• $s_i$ 是“G”或“B”，表示顶点 $i$ 上石头的颜色。“G”代表绿色，“B”代表蓝色。
• $1 \leq u_i, v_i \leq N$
• $0 \leq w_i \leq 10^5$
• 给定的图满足“双子树”的条件。
• $1 \leq Q \leq 10^5$
• $1 \leq e_j \leq N - 1$
• $1 \leq a_j \leq 10^5$

输出格式

输出 $Q$ 行答案。在第 $j$ 行，输出第 $j$ 次操作后树的价值。每行末尾请添加换行符。

5
GBBBB
1 2 0
1 3 0
2 4 0
2 5 0
5
1 1
2 3
3 3
4 10
2 2

0
1
1
3
4

5
BGBGB
1 2 0
1 3 0
2 4 0
2 5 1000
4
4 1
3 1
1 1
2 1

0
1
3
4

7
GGGBBBB
1 5 1
2 5 1
7 5 0
7 6 0
3 6 0
4 6 0
6
5 1
5 1
5 1
6 3
3 3
5 100000

1
2
2
3
6
11

提示

在样例输入 1 中，只有一颗绿色石头。因此，问题是以最小成本将其移动到其中一个叶子节点。

翻译由 DeepSeek V3.2 完成