27093번 - 비밀 기지

문제

설곽국은 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$의 형태로 주어진다. $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$로 가장 적은 수의 도로를 이용해 이동할 때 지나는 도로의 개수이다.