Description

Given a tree with $n$ nodes, each node has a weight.

There are $m$ operations. In each operation, you are given $x, y$, which means changing the weight of node $x$ to $y$.

After each operation, you need to output the total weight of the maximum weight independent set of this tree.

Input Format

The first line contains two integers, representing the number of nodes $n$ and the number of operations $m$.

The second line contains $n$ integers. The $i$-th integer is the weight $a_i$ of node $i$.

In the next $(n - 1)$ lines, each line contains two integers $u, v$, indicating that there is an edge connecting $u$ and $v$.

In the next $m$ lines, each line contains two integers $x, y$, indicating an operation that changes the weight of node $x$ to $y$.

Output Format

For each operation, output one line with one integer representing the answer.

10 10
-11 80 -99 -76 56 38 92 -51 -34 47 
2 1
3 1
4 3
5 2
6 2
7 1
8 2
9 4
10 7
9 -44
2 -17
2 98
7 -58
8 48
3 99
8 -61
9 76
9 14
10 93

186
186
190
145
189
288
244
320
258
304

Hint

Constraints

• For $30\%$ of the testdata, $n, m \le 10$.
• For $60\%$ of the testdata, $n, m \le 10^3$.
• For $100\%$ of the testdata, $1 \le n, m \le 10^5$, $1 \leq u, v, x \leq n$, and $-10^2 \leq a_i, y \leq 10^2$.

Translated by ChatGPT 5