动态 DP

题目描述

给定一棵有 $n$ 个节点的树，每个节点 $i$ 有一个整数权值 $a_i$。

你需要依次执行 $m$ 次修改。每次修改给定两个整数 $x,y$，把节点 $x$ 的权值改为 $y$。在每次修改之后，求当前树的最大权独立集权值。

树的一个独立集是一个节点集合，其中任意两个节点之间都没有边直接相连。独立集的权值等于其中所有节点权值之和。允许选择空集，因此答案不会小于 $0$。

输入格式

第一行包含两个整数 $n,m$，分别表示节点数和修改次数。

第二行包含 $n$ 个整数，第 $i$ 个整数表示节点 $i$ 的初始权值 $a_i$。

接下来 $n-1$ 行，每行包含两个整数 $u,v$，表示树中有一条连接节点 $u,v$ 的边。

接下来 $m$ 行，每行包含两个整数 $x,y$，表示把节点 $x$ 的权值修改为 $y$。

输出格式

对于每次修改，输出一行一个整数，表示修改后整棵树的最大权独立集权值。

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

数据范围

对于全部数据，$1\le n,m\le 10^5$，$1\le u,v,x\le n$，$-100\le a_i,y\le 100$。输入的 $n-1$ 条边构成一棵树。