비밀 기지

설곽국은 1부터 $N$까지 번호가 매겨진 $N$개의 도시로 이루어진 국가이다. 도시 사이에는 두 도시를 연결하는 $N-1$개의 도로가 있으며, 모든 도시는 서로 연결되어 있다. 모든 도로의 길이는 $1$로 같다.

어느 날 이웃 나라 경곽국이 침공한다는 소식이 들려오자, 긴장한 설곽국 사람들은 비밀 기지를 하나 짓기로 했다. 비밀 기지는 임시로 간단하게 짓기 때문에 쉽게 위치를 옮길 수 있다.

비밀 기지는 다음 성질을 만족하는 도시에 짓는다.

• 비밀 기지를 $x$번 도시에 지었을 때, 모든 사람이 $x$번 도시로 이동하는 거리의 합을 $f(x)=\sum_{i=1}^n A_i \times \text{dist}(i, x)$로 정의한다. 이때 $\text{dist}(x, y)$는 $x$번 도시와 $y$번 도시 사이의 거리이다.
• 비밀 기지는 모든 도시 중 $f(x)$가 최소가 되는 도시 $x$에 짓는다. 이러한 도시가 여러 개라면 아무 곳에나 지어도 된다.

설곽국에 사는 브루는 비밀 기지를 짓고 나서 사람들의 이동 거리 총합을 알고 싶어 한다.

그런데 시간이 지남에 따라 정확히 $Q$번, 어떤 도시에 있는 사람의 수가 변한다. 변화가 일어날 때마다 이동 거리 총합이 바뀔 수 있고, 그 때문에 비밀 기지가 이동할 수도 있다. 각 시점에 대해 이동 거리 총합을 모두 구하라.

첫 줄에는 도시의 개수 $N$과 변화 횟수 $Q$가 주어진다.

둘째 줄에는 각 도시에 있는 사람의 수 $A_1$, $A_2$, $\cdots$, $A_N$이 공백으로 구분되어 주어진다.

셋째 줄부터 $N-1$개의 줄에는 설곽국의 도로 구조가 주어진다. $i$번째 줄에는 두 정수 $x_i$, $y_i$가 주어지며, 이는 $x_i$번 도시와 $y_i$번 도시를 잇는 도로가 있다는 뜻이다.

$N+2$번째 줄부터 $Q$개의 줄에는 변화가 $v_i$ $d_i$의 형태로 주어진다. $v_i$번 도시에 있는 사람의 수가 $d_i$명으로 바뀐다는 뜻이다.

초기 상태와, $Q$번의 인구 변화가 일어난 뒤 각각에 대해 모든 사람의 비밀 기지로의 이동 거리 합을 $Q+1$줄에 걸쳐 출력한다.

• $2 \le N \le 2 \times 10^5$
• $2 \le Q \le 2 \times 10^5$
• $1 \le A_i \le 10^6$ ($1 \le i \le N$)
• $1 \le x_i \le N$
• $1 \le y_i \le N$
• 입력으로 올바른 트리가 주어짐이 보장된다.
• $1 \le v_i \le N$ ($1 \le i \le Q$)
• $1 \le d_i \le 10^6$ ($1 \le i \le Q$)

두 도시 $a$와 $b$의 거리는 도시 $a$에서 도시 $b$로 가장 적은 수의 도로를 이용해 이동할 때 지나는 도로의 개수이다.