Subtree Weight Square Sum Queries on a Tree

You are given a tree with n nodes, where each node has an integer weight. The tree is undirected and connected. You are also given q operations. Each operation is one of the following:

• Update Operation: Change the weight of a node.
• Query Operation: Given a node u, consider the tree re-rooted at u. For each node v in this rooted tree, let \(S(v)\) be the sum of the weights in the subtree of v (including v itself). The answer to the query is the sum of the squares of these subtree sums, i.e., \[ \sum_{v\,\in\,T_u} \bigl(S(v)\bigr)^2 \] where \(T_u\) denotes the tree when rooted at u.

If the description is confusing, please refer to the sample explanation.

Note: All formulas are given in LaTeX format.

inputFormat

The first line contains two integers n and q: the number of nodes and the number of operations.

The second line contains n integers \(w_1, w_2, \dots, w_n\) representing the initial weights of the nodes.

Each of the next n-1 lines contains two integers \(u\) and \(v\) denoting an edge between nodes \(u\) and \(v\).

The following q lines describe the operations. An operation is in one of the two formats:

• 1 u x: Update the weight of node \(u\) to \(x\).
• 2 u: Query the sum of squares of subtree sums when the tree is rooted at node \(u\).

outputFormat

For each query operation (i.e. operations of type 2), output one line containing the corresponding answer, which is the sum of the squares of the subtree sums when the tree is rooted at the given node.

sample

1 1
5
2 1

25