트럭 운전사

헝가리는 0번부터 N-1번까지 번호가 붙은 $N$개의 도시로 이루어진 나라다.

도시들은 0번부터 $N - 2$번까지 번호가 붙은 $N - 1$개의 양방향 도로로 연결되어 있다. $j$번 도로($0 \le j \le N - 2$)는 도시 $U[j]$와 도시 $V[j]$를 잇고, 길이는 $T[j]$다. 즉, 이 도로를 지나는 데 $T[j]$의 시간이 걸린다. 각 도로는 서로 다른 두 도시를 잇고, 두 도시를 잇는 도로는 많아야 하나다.

서로 다른 두 도시 $a$와 $b$ 사이의 경로는 서로 다른 도시들의 수열 $p_0, p_1, \dots, p_l$이다. 이때 $p_0 = a$, $p_l = b$이고, 각 $i$($0 \le i < l$)에 대해 도시 $p_i$와 $p_{i+1}$을 잇는 도로가 있어야 한다. 임의의 두 도시 사이에는 경로가 있으며, 두 도시 사이의 경로는 하나뿐이다.

도시 $a$와 $b$의 거리를 $d(a, b)$로 쓰며, 다음과 같이 정의한다. $a = b$이면 $d(a, b) = 0$이다. 그렇지 않으면 $d(a, b)$는 $a$와 $b$ 사이 경로에 있는 도로 길이의 합이다.

Karcsi는 트럭 운전사로, 여러 도시에서 배달을 완료해야 한다. $0$부터 $N - 1$까지의 각 $i$에 대해, Karcsi는 도시 $i$에서 $W[i]$번의 배달을 해야 한다. Karcsi는 도시 $0$에서 출발하며, 배달은 어떤 순서로 해도 된다. 배달을 마치면 도시 $0$으로 돌아온다. 배달 계획은 도시들의 수열 $c_1, c_2, \dots, c_m$(비어 있을 수도 있음)이며, 각 $i$($0 \le i < N$)에 대해 도시 $i$가 정확히 $W[i]$번 나타나야 한다.

계획 $c_1, c_2, \dots, c_m$의 배달 시간은 수열 $0, c_1, c_2, \dots, c_m, 0$에서 이웃한 도시 사이 거리의 합이다. 즉 $d(0, c_1) + d(c_1, c_2) + \cdots + d(c_m, 0)$이다.

Karcsi는 $Q$일 동안 일한다. 하루가 시작될 때마다 한 도시에서 필요한 배달 횟수가 바뀐다. 어떤 도시 $S$와 음이 아닌 정수 $X$에 대해 $W[S]$의 값이 $X$가 된다. 이후 다시 바뀌기 전까지 $W[S]$의 값은 $X$로 유지된다.

Karcsi는 시급으로 임금을 받기 때문에, 배달 시간이 가장 길어지는 계획을 고르고 싶어 한다. 각 날에 대해, 가능한 모든 계획 중 최대 배달 시간을 구하라.

• $2 \le N \le 100000$
• $0 \le U[j] < V[j] < N$ (각 $j$($0 \le j \le N - 2$)에 대해)
• $1 \le T[j] \le 100$ (각 $j$($0 \le j \le N - 2$)에 대해)
• 도로를 이용하면 임의의 도시에서 다른 임의의 도시로 이동할 수 있다.
• $0 \le W[i] \le 10^6$ (각 $i$($0 \le i < N$)에 대해)
• $1 \le Q \le 300000$
• $0 \le S < N$
• $0 \le X \le 10^6$