【模板】"动态DP"&动态树分治(加强版)

题目背景

树剖常数小!跑不满! shadowice1984 为了向你证明他能卡树剖并且会卡树剖从而出了这道毒瘤题 保证答案均在int范围内 然后就被离线算法针对了…… 因此这道题变成了强制在线

题目描述

同 [P4719](https://www.luogu.org/problemnew/show/P4719) 给定一个 $n$ 个点的带点权树,进行 $m$ 次修改点权的操作 你需要在每次修改之后输出树上最大带权独立集的权值之和

输入输出格式

输入格式


同 [P4719](https://www.luogu.org/problemnew/show/P4719) 第一行两个正整数 $n$ , $m$ 表示树的点数和总操作个数 第二行n个整数 $V_{1}...V_{n}$ 表示每个点的点权 接下来m行每行两个整数 $x,y$表示将x的点权修改为y 对于第1行,x即为被操作的点的编号 对于第2到m行,被操作的点的编号=x^lastans 其中lastans是上一次操作后输出的答案,^表示按位异或操作

输出格式


输出$m$行,第$i$行表示表示第$i$次操作之后树上最大带权独立集的权值和

输入输出样例

输入样例 #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
184 -17
184 98
185 -58
153 48
190 99
296 -61
253 76
329 14
264 93

输出样例 #1

186
186
190
145
189
288
244
320
258
304

说明

数据范围 $n \leq 1*10^6$,$m \leq 3*10^6$ 时限为标程的二倍,如果卡常数的话请使用int类型