28425번 - 점수 계산하기

당신은 직원의 점수를 관리하는 프로그램을 만들고 있다. 회사의 조직도는 각 직원이 노드고 직속 상사가 부모 노드인 트리 형태로 나타낼 수 있다. 이 트리의 루트는 사장이다.

이 프로그램은 각 직원에게 두 가지의 점수를 부여한다. 하나는 그 직원이 얻게 되는 $score$, 다른 하나는 특정 직원이 $score$를 얻었을 때 그 직원을 의미하는 노드의 조상들이 받게 되는 $bonus$ 점수다. 만약 특정 직원이 $x$만큼의 $score$를 얻는다면, 그 직원을 의미하는 노드의 조상 노드들은 모두 $x$만큼의 $bonus$ 점수를 얻게 된다.

이 프로그램을 이용하려는 회사에서 요구조건이 하나 생겼다. 바로 사장이 바뀌면 간선은 모두 유지하면서 그 사장을 루트로 하는 새로운 트리를 만든 뒤, 각 직원의 $bonus$를 초기화하고 기존 $score$를 이용해 새로운 트리에서 직원의 점수를 다시 계산해달라는 것이다.

예를 들어, 위와 같은 상황을 보자. 위 그림에서 노드 안의 수는 노드의 번호, 노드 옆의 작은 수는 그 노드의 $score$를 의미한다.

그림처럼 $1$번 노드가 루트인 상황에서 $3$번 노드의 점수는 $3$번 노드의 $score$인 $47$점과, $4$번 노드가 $18$만큼의 $score$를 얻으며 그 조상 노드가 얻게 된 $18$만큼의 $bonus$ 점수가 합쳐진 $65$점이 된다.

그런데 만약 루트를 $5$번으로 바꾼다면 트리의 형태가 위와 같이 변하게 된다. 이때 $2$번 노드의 점수를 구해보면 $2$번 노드의 $score$인 $16$점과, $1$, $3$, $4$번 노드가 각각 $score$를 얻을 때 $2$번 노드가 같이 얻게 되는 $43$, $47$, $18$의 $bonus$가 더해져 총 $124$점이 된다.

위와 같은 경우들을 처리하기 위해 우리는 트리와 각 직원이 직접 받은 점수가 주어진 상황에서 아래와 같은 질의를 $Q$번 처리해야 한다.

• $r$ $v$: $r$번 노드가 루트일 때 $v$번 직원의 점수

질의들이 주어질 때, 각 질의의 정답을 구하는 프로그램을 작성하시오.

첫째 줄에 노드의 수 $N$과 질의의 수 $Q$가 공백으로 구분되어 주어진다. $(1 \le N \le 100\,000;$ $1 \le Q \le 100\,000)$

둘째 줄에 $1$번 직원부터 $N$번 직원까지 순서대로 각 직원이 얻은 $score$가 공백으로 구분되어 주어진다. $(0 \le score \le 10\,000)$

셋째 줄부터 $N - 1$줄에 걸쳐 트리의 간선 정보를 의미하는 $u, v$가 공백으로 구분되어 주어진다. $(1 \le u, v \le N)$

그리고 $Q$개의 줄에 걸쳐 문제에 제시된 질의가 주어진다.

주어지는 그래프는 트리이다.

각 질의의 정답을 한 줄에 하나씩 입력받은 순서대로 출력한다.