트럭 운전사

헝가리에는 $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,\ldots,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$으로 돌아온다. 배달 계획은 각 $i$ ($0 \le i < N$)에 대해 도시 $i$를 정확히 $W[i]$번 포함하는 도시들의 (비어 있을 수도 있는) 수열 $c_1,c_2,\ldots,c_m$이다.

계획 $c_1,c_2,\ldots,c_m$의 배달 시간은 수열 $0,c_1,c_2,\ldots,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는 시간당 보수를 받는다. 그는 가능한 모든 계획 중 배달 시간이 최대가 되도록 배달 계획을 선택하려 한다. Karcsi가 일해야 하는 각 날짜의 최대 배달 시간을 계산하는 것이 여러분의 과제이다.

구현 세부사항

두 개의 프로시저를 구현해야 한다.

void init(int N, int[] U, int[] V, int[] T, int[] W)

• $N$: 도시의 수.
• $U,V$: 도로의 연결 관계를 나타내는 길이 $N-1$의 배열.
• $T$: 도로 길이를 나타내는 길이 $N-1$의 배열.
• $W$: 각 도시의 배달 횟수를 나타내는 길이 $N$의 배열.
• 이 프로시저는 각 테스트 케이스마다 max_time을 호출하기 전에 정확히 한 번 호출된다.

int64 max_time(int S, int X)

• $S,X$: 배달 횟수의 변경을 나타내는 정수. $W[S]$의 값을 $X$로 설정해야 한다.
• 이 프로시저는 먼저 지정된 갱신을 수행한 다음, 가능한 모든 배달 계획 중 최대 배달 시간을 반환해야 한다.
• 이 프로시저는 정확히 $Q$번 호출된다.

예제

다음 호출 수열을 살펴보자.

init(5, [0, 0, 1, 1], [1, 2, 3, 4], [1, 2, 3, 1], [0, 0, 1, 0, 1])

매개변수들은 아래의 도로망에 해당한다. 빨간색 숫자는 각 도시의 초기 배달 횟수를 나타낸다.

max_time(0, 1)

갱신 후에는 $W=[1,0,1,0,1]$이다. 가능한 배달 계획 하나는 수열 $4,2,0$이다. 이 경우 Karcsi는 도시 $0,4,2,0,0$을 이 순서로 방문하며, 배달 시간은 $d(0,4)+d(4,2)+d(2,0)+d(0,0)=2+4+2+0=8$이다.

배달 시간이 $8$보다 큰 배달 계획은 없으므로, 프로시저는 $8$을 반환해야 한다.

max_time 호출의 추가 예시는 다음 표에 정리되어 있다.

제약 조건

• $2 \le N \le 100\,000$
• $0 \le U[j] < V[j] < N$ ($0 \le j \le N-2$인 각 $j$에 대해)
• $1 \le T[j] \le 1000$ ($0 \le j \le N-2$인 각 $j$에 대해)
• 도로를 이용하여 어떤 도시에서든 다른 모든 도시로 이동할 수 있다.
• $0 \le W[i] \le 10^6$ ($0 \le i < N$인 각 $i$에 대해)
• $1 \le Q \le 300\,000$
• $0 \le S < N$
• $0 \le X \le 10^6$

서브태스크

1. (8점) $N=2$
2. (21점) $N,Q \le 1000$
3. (14점) $0 \le j \le N-2$인 각 $j$에 대해 $U[j]=\left\lfloor\frac{j}{2}\right\rfloor$이고 $V[j]=j+1$이다.
4. (21점) $0 \le j \le N-2$인 각 $j$에 대해 $U[j]=j$이고 $V[j]=j+1$이다.
5. (36점) 추가 제약 조건이 없다.

샘플 그레이더는 다음 형식으로 입력을 읽는다.

• 1번째 줄: $N\ Q$
• 2번째 줄: $U[0]\ U[1]\ \ldots\ U[N-2]$
• 3번째 줄: $V[0]\ V[1]\ \ldots\ V[N-2]$
• 4번째 줄: $T[0]\ T[1]\ \ldots\ T[N-2]$
• 5번째 줄: $W[0]\ W[1]\ \ldots\ W[N-1]$
• $6+k$번째 줄 ($0 \le k < Q$): 갱신 $k$에 대한 $S\ X$

샘플 그레이더는 다음 형식으로 답을 출력한다.

• $1+k$번째 줄 ($0 \le k < Q$): 갱신 $k$ 이후 max_time의 반환값