Gemini Tree (Ver.Jadeite)

각 정점에 초록색 또는 파란색 돌이 하나씩 놓인 트리를 생각한다. 이 트리는 아래 연산 1과 연산 2를 수행한 뒤 조건 3을 만족할 수 있으면 "Gemini Tree"라고 부른다.

1. 먼저 간선으로 직접 연결된 정점 쌍을 골라, 두 끝점에 놓인 돌을 서로 바꾼다. 이 연산을 0회 이상 원하는 만큼 반복한다.
2. 다음으로 간선을 최대 1개 골라 삭제한다.
3. 이때 트리는 최대 두 개의 연결 요소로 나뉘고, 각 연결 요소에는 한 종류의 돌만 있다.

각 간선에 길이가 주어진 Gemini Tree의 값을 다음과 같이 정의한다.

1. 먼저 간선으로 직접 연결된 정점 쌍을 골라, 끝점에 놓인 돌을 서로 바꾼다. 이 연산을 0회 이상 반복한다. 한 번 바꿀 때마다 드는 비용은 그 간선의 길이와 같다.
2. 다음으로 간선을 최대 1개 골라 삭제한다.
3. 이때 트리는 최대 두 개의 연결 요소로 나뉘고, 각 연결 요소에는 한 종류의 돌만 있다.
4. 조건 3을 만족하는 데 필요한 연산 1의 총비용의 최솟값이 이 트리의 값이다.

값을 계산할 때 돌은 실제로 이동하지 않는다.

정점이 $N$개인 Gemini Tree가 주어진다. $N$은 홀수이다. $i$번째 간선은 정점 $u_i$와 $v_i$를 잇고, 길이는 $w_i$이다. 정점에 놓인 돌의 색은 문자열 $S = s_1s_2\dots s_N$으로 주어지며, $s_i$는 정점 $i$의 돌 색이다.

이 트리에 대해 $Q$번의 연산을 순서대로 수행한다. $j$번째 연산은 두 정수 $e_j$, $a_j$로 주어지며, $e_j$번째 간선의 길이를 $a_j$만큼 늘린다. 이 변경은 이후 연산에도 그대로 유지된다. 각 연산 후 트리의 값을 출력한다.

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

$Q$개의 줄을 출력한다. $j$번째 줄에는 $j$번째 연산을 수행한 후 트리의 값을 출력한다. 각 줄의 끝에는 줄바꿈을 넣는다.

• 모든 입력은 정수이다.
• $3 \le N \le 10^5$
• $N$은 홀수이다.
• $s_i$는 "G" 또는 "B"이며, 정점 $i$의 돌 색을 나타낸다. "G"는 초록색, "B"는 파란색이다.
• $1 \le u_i, v_i \le N$
• $0 \le w_i \le 10^5$
• 주어진 그래프는 Gemini Tree이다.
• $1 \le Q \le 10^5$
• $1 \le e_j \le N-1$
• $1 \le a_j \le 10^5$

첫 번째 샘플에는 초록색 돌이 하나뿐이다. 따라서 이 문제는 그 돌을 최소 비용으로 잎 정점 중 하나로 옮기는 문제이다.