Background

Tree decomposition has small constants! It cannot reach full performance!

shadowice1984 made this nasty problem to prove to you that he can hack tree decomposition and knows how to do it.

It is guaranteed that all answers fit in the int range.

Then it got targeted by offline algorithms...

So this problem becomes forced online.

Problem 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