本题数据面向线段树版本

全局平衡二叉树版本指路该 oj lg4719

【题目描述】

给定一棵 $n$ 个点的树，每个点的初始点权为 $V_i$。

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

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

【输入格式】

第一行，$n,m$，分别代表点数和操作数。

下来 $n$ 个点的权值$V_i$ 。

接下来 $n-1$ 行，每行两个整数 $x,y$ ，表示树的一条边。

接下来 $m$ 行，$x,y$ ，表示修改点 $x$ 的权值为 $y$。

【输出格式】

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

【输入样例】

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

【输出样例】

186
186
190
145
189
288
244
320
258
304