Maximum Weighted Independent Set on a Tree with Updates

You are given a tree with n nodes, where each node has an associated weight. The tree is provided as an undirected connected graph. You need to perform m update operations on the node weights. After each update, compute and output the maximum sum of weights of an independent set on the tree.

An independent set is a set of nodes with no two adjacent (i.e. there is no edge connecting any two nodes in the set). Note that selecting the empty set (with sum 0) is allowed.

The standard dynamic programming recurrence for trees can be used if the tree is rooted at node 1. Let \(dp[u][0]\) be the maximum sum for the subtree of node \(u\) when \(u\) is not selected, and \(dp[u][1]\) be the maximum sum when \(u\) is selected. Then:

\(dp[u][0] = \sum_{v \in child(u)} \max(dp[v][0], dp[v][1])\)

\(dp[u][1] = weight(u) + \sum_{v \in child(u)} dp[v][0]\)

The answer for the tree is \(\max(dp[1][0], dp[1][1])\).

inputFormat

The input begins with a line containing two integers n and m (1 ≤ n, m ≤ 10⁵), representing the number of nodes and the number of update operations.

The second line contains n integers, where the i-th integer is the initial weight of node i.

Each of the following n-1 lines contains two integers u and v, denoting an edge between nodes u and v.

Each of the next m lines contains two integers u and w, indicating that the weight of node u should be updated to w.

outputFormat

For each update operation, output a single line containing the maximum weighted independent set sum of the tree after the update.

sample

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

11
11
8