P4719 [Template] Dynamic DP

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.

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$.

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

#### 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