Disconnecting Leaves in a Tree

Xiao A is faced with a mystical waterfall, modeled as a tree with n nodes. Each node i has an associated cost w_i (the cost required for climbing to and then removing that node). Xiao A wants to cut off (i.e. remove some nodes) such that there is no path between the root of the tree and any leaf node. In other words, for every root‐to‐leaf path there must be at least one removed node, and the total removal cost should be minimized.

The process is complicated by two factors. First, Xiao A’s friend may change the terrain by updating the cost of a node. Second, instead of processing the entire tree every time, Xiao A restricts his operation to a subtree (which is completely independent of the rest of the tree). In a subtree query, you are given a node u; consider the subtree rooted at u (using the tree rooted at node 1), and compute the minimum cost to disconnect u from all of its leaves.

The removal cost, denoted by dp(u), is defined recursively as follows:

If u is a leaf in the current subtree (i.e. it has no children), then \[ dp(u)=w_u, \] otherwise \[ dp(u)=\min\Bigl(w_u, \sum_{v\in child(u)}dp(v)\Bigr). \]

You are to process two types of queries on the tree:

• Update Query: "1 u new_weight" where the cost of node u is updated to new_weight.
• Subtree Query: "2 u" where you need to compute and output dp(u) for the subtree rooted at node u.

The tree is initially provided with n nodes and n-1 edges, and is rooted at node 1.

inputFormat

The input begins with a line containing two integers n (the number of nodes) and q (the number of queries).

The next line contains n space‐separated integers w₁, w₂, …, w_n representing the initial cost for each node.

Then follow n-1 lines, each containing two integers u and v which describe an edge between nodes u and v. The tree is undirected but is rooted at node 1.

Then follow q lines, each describing a query in one of the following two formats:

• 1 u new_weight: update the cost of node u to new_weight.
• 2 u: output the minimum cost to disconnect node u (as the root of its subtree) from all its leaves.

outputFormat

For each query of the second type, output a single line containing the minimum removal cost for the specified subtree.

sample

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

3
2
3

</p>