방어 타워

ICPCCamp에는 $1, 2, \dots, n$ 번호가 붙은 $n$개의 도시가 있으며, $(n - 1)$개의 양방향 도로로 연결되어 있다. 서로 다른 두 도시 사이의 경로는 정확히 하나이다.

도시 $i$에는 power가 $a_i$인 방어 타워가 있다. 타워는 $n, (n - 1), \dots, 1$ 순서로 지어졌고, 타워 번호는 도시 번호와 같다. 따라서 타워 $n$이 가장 오래된 타워이고 타워 $1$이 가장 새로운 타워이다. 타워 $i$가 도시 $j$에 주는 효과는 $\mathit{eff}(i, j) = a_i - \delta(i, j)$이다. 여기서 $\delta(i, j)$는 도시 $i$와 $j$ 사이의 도로 수다. 도시 $j$의 수호자는 $j$에 대한 효과가 가장 큰 타워다. 여러 타워의 효과가 같으면 그중 가장 오래된 타워가 수호자가 된다.

Yuuka는 방어 타워의 power를 올리는 명령을 $q$번 내린다. $k$번째 명령은 타워 $w_k$의 power에 $d_k$를 더한다. 명령을 처리할 때마다 모든 도시 수호자 번호의 합을 구하려 한다. 강화된 타워는 자동으로 가장 새로운 타워가 된다.

다만 강화에는 비용이 든다. 강화 대상 타워가 자기 도시의 수호자가 아니거나 $d_k = 0$이면, 그 명령은 무시된다.

입력에는 0개 이상의 테스트 케이스가 들어 있으며, 파일의 끝에서 끝난다. 각 테스트 케이스는 다음과 같다.

첫째 줄에 두 정수 $n$, $q$ ($1 \leq n, q \leq 10^5$)가 주어진다.

둘째 줄에 $n$개의 정수 $a_1, a_2, \dots, a_n$ ($0 \leq a_i \leq 10^9$)이 주어진다.

이어지는 $n - 1$개의 줄에는 정수 $u_i$, $v_i$ ($1 \leq u_i, v_i \leq n$)가 주어지며, 도시 $u_i$와 $v_i$를 잇는 도로가 있음을 뜻한다. 서로 다른 두 도시 사이의 경로는 정확히 하나이다.

마지막 $q$개의 줄에는 정수 $w_k$, $d_k$ ($1 \leq w_k \leq n$, $0 \leq d_k \leq 10^9$)가 주어진다.

모든 테스트 케이스에 걸쳐 $n$의 합과 $q$의 합은 각각 $10^5$를 넘지 않는다.

각 테스트 케이스마다 $q$개의 정수 $s_1, s_2, \dots, s_q$를 출력한다. $s_k$는 $k$번째 명령을 처리한 뒤 모든 수호자 번호의 합이다.