P4751 [Template] Dynamic DP (Enhanced Version)

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.

Same as [P4719](https://www.luogu.com.cn/problem/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.

Same as [P4719](https://www.luogu.com.cn/problem/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 $m$ lines. The $i$-th line is the total weight of the maximum weight independent set on the tree after the $i$-th operation.

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