점수 계산하기

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

이 프로그램은 각 직원에게 두 가지 점수를 부여한다. 하나는 그 직원이 얻는 $score$이고, 다른 하나는 어떤 직원이 $score$를 얻었을 때 그 직원을 나타내는 노드의 조상들이 받는 $bonus$ 점수다. 어떤 직원이 $x$만큼의 $score$를 얻으면, 그 직원 노드의 모든 조상 노드는 $x$만큼의 $bonus$를 얻는다.

회사에 새로운 요구사항이 생겼다. 사장이 바뀌면 간선은 모두 유지한 채 새 사장을 루트로 하는 트리를 만든다. 그다음 각 직원의 $bonus$를 초기화하고, 기존 $score$를 이용해 새 트리에서 직원의 점수를 다시 계산한다.

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

그림처럼 1번 노드가 루트일 때 3번 노드의 점수는 3번 노드의 $score$인 47점에, 4번 노드가 얻은 $score$ 18이 $bonus$로 더해진 65점이다.

루트를 5번 노드로 바꾸면 트리 모양이 위와 같이 바뀐다. 이때 2번 노드의 점수는 2번 노드의 $score$인 16점에, 1, 3, 4번 노드가 각각 $score$를 얻을 때 2번 노드가 받는 $bonus$ 43, 47, 18을 더한 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$개의 줄에 문제에서 제시한 질의가 주어진다.

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

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