Dynamic Maximum Weighted Independent Set on Trees

Given a tree with (n) nodes where each node has an associated weight, and (m) update operations, each update changes the weight of a node. After each update, you are required to compute the maximum weight of an independent set in the tree.

An independent set in a tree is a set of nodes such that no two adjacent nodes are selected. The empty set is allowed and is considered to have a weight of 0.

Assume the tree is rooted at node 1. Let (dp[u][1]) denote the maximum weight of an independent set in the subtree rooted at (u) if (u) is selected, and (dp[u][0]) if it is not. They can be computed using the following recurrences:

[ \begin{aligned} \text{dp}[u][1] &= w_u + \sum_{v \in \text{child}(u)} dp[v][0], \ \text{dp}[u][0] &= \sum_{v \in \text{child}(u)} \max\big(dp[v][0],, dp[v][1]\big). \end{aligned} ]

The answer for the whole tree is (\max\big(dp[1][0], dp[1][1]\big)). Note that since the empty set is allowed, the answer is always at least 0.

After each update, where the weight of a node (x) is set to (y), you need to recalculate these values and output the new maximum weight independent set of the tree.

inputFormat

The first line contains two integers (n) and (m), denoting the number of nodes and the number of operations respectively.\n\nThe second line contains (n) integers, where the (i)-th integer represents the initial weight of node (i).\n\nThe following (n-1) lines each contain two integers (u) and (v), representing an edge between nodes (u) and (v) (the tree is undirected).\n\nThe next (m) lines each contain two integers (x) and (y), meaning that in the operation the weight of node (x) is updated to (y).

outputFormat

Output (m) lines. Each line should contain one integer representing the maximum weight of an independent set in the tree after the corresponding update.

sample

3 1
1 2 3
1 2
1 3
2 5

8