Tree Modification and Subtree Distance Sum

You are given a rooted tree with (n) nodes (indexed from (1) to (n)) whose root is node (1). Each node (i) has a weight (v_i). In the tree, for any node (y), define [ f(y)=\sum_{x\in \operatorname{subtree}(y)} \operatorname{dist}(x,y)\cdot v_x, ] where (\operatorname{subtree}(y)) is the set of nodes in the subtree of (y) (including (y) itself) and (\operatorname{dist}(x,y)) denotes the number of edges on the shortest path between (x) and (y).

There are (q) independent operations. In each operation, you are given two distinct nodes (x) and (y) with the guarantee that (x\in \operatorname{subtree}(y)) and (x\neq y). The operation is processed on the original tree (i.e. the operations do not affect each other) as follows:

1. Attach all children of (x) to (x)’s parent (i.e. reassign each child of (x) to be a child of (p(x))).
2. Remove node (x) from the tree.
3. Among the children of (y) in the original tree, let (z) be the unique child such that (x) lies in the subtree of (z) (this can be determined using an Euler tour on the original tree). Insert node (x) between (y) and (z); that is, make (x) a child of (y) and make (z) a child of (x).
4. Output (f(y)) for the modified tree.

Note that if (y) is the parent of (x) (i.e. (y=p(x)) in the original tree), then the tree remains unchanged and you should simply output (f(y)) on the original tree.

Your task is to process all (q) operations and for each operation compute (f(y)) on the modified tree.

inputFormat

The input is given as follows:

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

The second line contains (n) integers (v_1, v_2, \dots, v_n) ((1\le v_i\le 10^9)) representing the weight of each node.

The next (n-1) lines each contain two integers (u) and (v) ((1\le u,v\le n)), indicating that there is an edge from node (u) (the parent) to node (v) (the child). It is guaranteed that the tree is rooted at node (1).

Each of the next (q) lines contains two integers (x) and (y) with (x\in \operatorname{subtree}(y)) and (x\neq y), representing one operation.

outputFormat

For each query, output a single line containing the value of (f(y)) after performing the described operation on a copy of the original tree.

sample

5 2
1 2 3 4 5
1 2
1 3
2 4
2 5
4 1
4 2

26
9