9483 - 动态dp

讨论

统计

通过次数

提交次数

旧版界面

时间限制 : 2 秒

内存限制 : 256 MB

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

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

你需要在每次操作之后求出这棵树的最大权独立集的权值大小。（即一条边最多选择其中一个节点的权值）

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

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

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

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

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

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

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

模板