【模板】动态 DP

题目描述

给定一棵$n$个点的树,点带点权。 有$m$次操作,每次操作给定$x,y$,表示修改点$x$的权值为$y$。 你需要在每次操作之后求出这棵树的最大权独立集的权值大小。

输入输出格式

输入格式


第一行,$n,m$,分别代表点数和操作数。 第二行,$V_1,V_2,...,V_n$,代表$n$个点的权值。 接下来$n-1$行,$x,y$,描述这棵树的$n-1$条边。 接下来$m$行,$x,y$,修改点$x$的权值为$y$。

输出格式


对于每个操作输出一行一个整数,代表这次操作后的树上最大权独立集。 保证答案在$int$范围内

输入输出样例

输入样例 #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

说明

对于30%的数据,$1\le n,m\le 10$ 对于60%的数据,$1\le n,m\le 1000$ 对于100%的数据,$1\le n,m\le 10^5$