P4751 【模板】动态 DP（加强版）

题目背景

树剖常数小！跑不满！

shadowice1984 为了向你证明他能卡树剖并且会卡树剖从而出了这道毒瘤题。

保证答案均在 int 范围内。

然后就被离线算法针对了……

因此这道题变成了强制在线。

题目描述

给定一棵 $n$ 个点的树，点带点权。

有 $m$ 次操作，每次操作给定 $x,y$，表示修改点 $x$ 的权值为 $y$。

你需要在每次操作之后求出这棵树的最大权独立集的权值大小。

输入格式

第一行有两个整数，分别表示结点个数 $n$ 和操作个数 $m$。

第二行有 $n$ 个整数，第 $i$ 个整数表示节点 $i$ 的权值 $a_i$。

接下来 $(n - 1)$ 行，每行两个整数 $u, v$，表示存在一条连接 $u$ 与 $v$ 的边。

接下来 $m$ 行，每行两个整数 $x,y$，表示一次操作，修改点 $x$ 的权值为 $y$。

输出格式

对于每次操作，输出一行一个整数表示答案。

输入输出样例 #1

输入 #1

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

输出 #1

186
186
190
145
189
288
244
320
258
304

说明/提示

数据规模与约定

• 对于 $100\%$ 的数据，保证 $1\le n\le 10^6,1 \le m \le 3 \times 10^6$，$1 \leq u, v , x \leq n$，$-10^2 \leq a_i, y \leq 10^2$。