P15709 [JAG 2023 Summer Camp #2] 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 \ldots 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.

$$ \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} $$ The input satisfies the following constraints: - All inputs consist of integers. - $3 \leq N \leq 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 \leq u_i, v_i \leq N$ - $0 \leq w_i \leq 10^5$ - The given graph satisfies the condition of "Gemini Tree." - $1 \leq Q \leq 10^5$ - $1 \leq e_j \leq N - 1$ - $1 \leq a_j \leq 10^5$

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.

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.