비밀 기지 | cho.sh

설곽국은 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$ 줄에 걸쳐 출력한다.

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