Description

Same as P4719.

Given a tree with $n$ nodes and node weights, perform $m$ operations that modify node weights.

After each modification, you need to output the maximum total weight of a maximum weight independent set on the tree.

Input Format

Same as P4719.

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

The second line contains $n$ integers $V_1,\dots,V_n$, representing the weight of each node.

The next $(n - 1)$ lines each contain two integers $u, v$, indicating that there is an edge connecting $u$ and $v$.

The next $m$ lines each contain two integers $x$, $y$, indicating that the weight of node $x$ is modified to $y$.

For the 1st operation, $x$ is the index of the modified node.

For the 2nd to the $m$-th operations, the index of the modified node is $x\oplus lastans$.

Here, $lastans$ is the answer output after the previous operation, and $\oplus$ denotes the bitwise XOR operation.

Output Format

Output $m$ lines. The $i$-th line is the total weight of the maximum weight independent set on the tree after the $i$-th operation.

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
184 -17
184 98
185 -58
153 48
190 99
296 -61
253 76
329 14
264 93

186
186
190
145
189
288
244
320
258
304

Hint

Constraints: $n \leq 1 \times 10^6$, $m \leq 3 \times 10^6$. It is guaranteed that at any time, the absolute value of each node weight is $\leq 100$.

The time limit is twice that of the reference solution. If you need to optimize constants, please use the int type.

Translated by ChatGPT 5