30357번 - Gemini Tree (Ver.Jadeite) 다국어

Consider a tree with a green or blue stone placed at 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, operate "selecting pairs of vertices that are directly connected by edges and exchanging the stones placed on each endpoint," any number of times from zero to more.
2. Second, select one or fewer edges and delete them.
3. At this time, the tree is divided into at most two connected components, and only one type of stone is placed in either.

Consider a "Gemini tree" with a specified length for each edge, and define its value as follows.

1. First, operate "selecting pairs of vertices that are directly connected by edges and exchanging the stones placed on each endpoint" any number of times from zero to more. Each exchange operation costs equal to the length of the edge.
2. Second, select one or fewer edges and delete them.
3. At this time, the tree is divided into at most two connected components, and only one type of stone is placed in either.
4. The minimum value of the total cost of operation 1 required to achieve condition 3 is the value of "Gemini Tree."

Note that stones are not moved when calculating the value.

You are given a "Gemini tree" with a specified length for each edge. It has $N$ vertices, where $N$ is an odd number. The $i$-th edge connects two vertices, $u_i$ and $v_i$, and has a length $w_i$. The stone colors placed on vertices represent the string $S = s_1s_2\dots s_N$.

You sequentially perform $Q$ operations on this tree. The $j$-th operation is defined by two integers $e_j$, $a_j$, which represents increasing the length of the $e_j$-th edge by $a_j$. The effect of the operation remains even in subsequent operations. Answer the value of the tree after each operation.

$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$

Output the answer in $Q$ lines. On the $j$-th line, output the value of the tree after the $j$-th operation. Add a new line at the end of each line.

• All inputs consist of integers.
• $3 \le N \le 10^5$
• $N$ is an odd number.
• $s_i$ is either "G" or "B" and represents the stone's color at vertex $i$. "G" represents green, and "B" represents blue.
• $1 \le u_i, v_i \le N$
• $0 \le w_i \le 10^5$
• The given graph satisfies the condition of "Gemini Tree."
• $1 \le Q \le 10^5$
• $1 \le e_j \le N-1$
• $1 \le a_j \le 10^5$

In Sample Input 1, there is one green stone. Therefore, the problem is to move this to one of the leaves at a minimal cost.