Defense Tower

In ICPCCamp, there are $n$ cities labeled $1, 2, \dots, n$, connected by $(n - 1)$ bidirectional roads. There is exactly one path between any two different cities.

Each city $i$ has a defense tower with power $a_i$. The towers were built in the order $n, (n - 1), \dots, 1$, and each tower has the same number as its city. So tower $n$ is the oldest and tower $1$ is the newest. The effect of tower $i$ on city $j$ is $\mathit{eff}(i, j) = a_i - \delta(i, j)$, where $\delta(i, j)$ is the number of roads between cities $i$ and $j$. The protector of city $j$ is the tower with the largest effect on $j$. If several towers tie on a city, the oldest one is its protector.

Yuuka issues $q$ commands that upgrade defense towers. The $k$-th command adds $d_k$ to the power of tower $w_k$. After each command, she wants the sum of the protectors' labels over all cities. The upgraded tower becomes the newest tower.

Upgrading is costly. If the tower being upgraded is not the protector of its own city, or if $d_k = 0$, the command is ignored.

The input has zero or more test cases and ends at end-of-file. Each test case is given as follows.

The first line contains two integers $n$ and $q$ ($1 \leq n, q \leq 10^5$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \leq a_i \leq 10^9$).

Each of the next $n - 1$ lines contains two integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n$), meaning there is a road between cities $u_i$ and $v_i$. There is exactly one path between any two different cities.

Each of the last $q$ lines contains two integers $w_k$ and $d_k$ ($1 \leq w_k \leq n$, $0 \leq d_k \leq 10^9$).

The sum of all $n$ and the sum of all $q$ over the test cases do not exceed $10^5$ each.

For each test case, output $q$ integers $s_1, s_2, \dots, s_q$, where $s_k$ is the sum of the protectors' labels after the $k$-th command.