Gemini Tree (Ver.Jadeite)

Consider a tree with a green or blue stone placed on each vertex. Such a tree is called a "Gemini Tree" if condition 3 can be satisfied after performing the following operations 1 and 2.

1. First, select pairs of vertices that are directly connected by an edge and exchange the stones on their two endpoints. Repeat this zero or more times.
2. Second, select at most one edge and delete it.
3. Then the tree splits into at most two connected components, and each component contains only one type of stone.

Consider a Gemini Tree where each edge has a given length, and define its value as follows.

1. First, select pairs of vertices that are directly connected by an edge and exchange the stones on their endpoints. Repeat this zero or more times. Each exchange costs the length of that edge.
2. Second, select at most one edge and delete it.
3. Then the tree splits into at most two connected components, and each component contains only one type of stone.
4. The value is the minimum total cost of operation 1 needed to satisfy condition 3.

Stones are not moved when computing the value.

You are given a Gemini Tree with $N$ vertices, where $N$ is odd. The $i$-th edge connects vertices $u_i$ and $v_i$ and has length $w_i$. The stone colors form the string $S = s_1s_2\dots s_N$, where $s_i$ is the color of vertex $i$.

You perform $Q$ operations on this tree in order. The $j$-th operation is given by two integers $e_j$ and $a_j$, and increases the length of the $e_j$-th edge by $a_j$. The change stays in effect for all later operations. After each operation, print the value of the tree.

$N$

$s_1s_2 \dots 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$

Print $Q$ lines. On the $j$-th line, print the value of the tree after the $j$-th operation. Print a newline at the end of each line.

• All inputs are integers.
• $3 \le N \le 10^5$
• $N$ is odd.
• $s_i$ is either "G" or "B", the color of vertex $i$. "G" means green and "B" means blue.
• $1 \le u_i, v_i \le N$
• $0 \le w_i \le 10^5$
• The given graph is a Gemini Tree.
• $1 \le Q \le 10^5$
• $1 \le e_j \le N-1$
• $1 \le a_j \le 10^5$

In the first sample, there is one green stone. Therefore, the problem is to move this stone to one of the leaves at minimal cost.