Calculating Scores

You are building a program that manages scores of employees. The org chart of a company can be represented as a tree, where each employee is a node and the direct supervisor is the parent node. The root of this tree is the president.

The program gives each employee two kinds of scores. One is the $score$ that the employee earns. The other is the $bonus$ score that the ancestors of the node representing an employee receive when that employee earns a $score$. If an employee earns $x$ of $score$, every ancestor node of that employee's node receives $x$ of $bonus$.

The company has a new requirement. When the president changes, keep all edges, build a new tree rooted at the new president, reset every employee's $bonus$, and recalculate each employee's score in the new tree using the existing $score$ values.

For example, consider the situation above. In the figure, the number inside each node is the node number, and the small number beside each node is its $score$.

As shown in the figure, when node 1 is the root, the score of node 3 is 65: its own $score$ of 47, plus the $bonus$ of 18 from node 4, which earns a $score$ of 18.

If the root is changed to node 5, the tree takes the shape shown above. Then the score of node 2 is 124: its own $score$ of 16, plus the $bonus$ values of 43, 47, and 18 that node 2 receives when nodes 1, 3, and 4 earn their $score$ values.

To handle such cases, the program must process the following query $Q$ times.

• $r$ $v$: the score of employee $v$ when node $r$ is the root

Write a program that finds the answer to each query, given the tree, the score of each employee, and the queries.

The first line contains the number of nodes $N$ and the number of queries $Q$, separated by a space. ($1 \le N \le 100\,000$; $1 \le Q \le 100\,000$)

The second line contains the $score$ of each employee from 1 to $N$, in order, separated by spaces. ($0 \le score \le 10\,000$)

The next $N - 1$ lines each contain $u$ and $v$, separated by a space, describing an edge of the tree. ($1 \le u, v \le N$)

The next $Q$ lines contain the queries.

The given graph is a tree.

Print the answer to each query on its own line, in the order the queries were given.