Maximum Connected Subtree Sum After Global Increase

You are given a rooted tree with \(n\) nodes numbered from \(1\) to \(n\), where the weight of the \(i\)-th node is \(a_i\). The tree is given as an undirected connected acyclic graph with \(n-1\) edges and is rooted at node \(1\).

The task is to answer \(q\) queries. In each query you are given a node \(u\) and an integer parameter \(x\). Suppose that we add \(x\) to the weight of every node (i.e. each node weight becomes \(a_i+x\)). In this modified tree, consider all connected subtrees that are completely contained in the subtree of \(u\) (with respect to the tree rooted at \(1\)) and that contain node \(u\) itself. You need to compute the maximum possible sum of the weights of the nodes in such a connected subtree.

The maximum sum for a node \(u\) (when all weights are increased by \(x\)) can be computed via the following recurrence:

[ f(u) = a_u + x + \sum_{v \in \text{child}(u)} \max(0, f(v)) ]

where \(\text{child}(u)\) are the children of \(u\) in the tree (after rooting the tree at node \(1\)).

Note: Even though the query adds the same constant \(x\) to every node, the choice of the connected subtree (which is allowed to pick or skip entire branches) depends on the trade‐off between the original weight \(a_i\) and the extra amount \(x\) (which is effectively multiplied by the number of nodes selected in that branch).

inputFormat

The first line contains two integers \(n\) and \(q\) \((1 \leq n, q \leq 10^5)\): the number of nodes and the number of queries.

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) \((|a_i| \leq 10^9)\) representing the initial weights of the nodes.

The next \(n-1\) lines each contain two integers \(u\) and \(v\) \((1 \le u, v \le n)\) denoting an edge of the tree.

The following \(q\) lines each contain two integers \(u\) and \(x\), where \(u\) is the node for the query and \(x\) is the integer that is added to every node's weight for that query \((|x| \le 10^9)\).

outputFormat

For each query, output a single integer: the maximum possible sum of weights of a connected subtree (after increasing every node's weight by \(x\)) that is completely contained within the subtree of node \(u\) and that contains node \(u\) itself.

sample

5 3
1 2 3 -1 2
1 2
1 3
2 4
2 5
1 0
2 2
3 -1

8
9
2