#P4751. 【模板】动态 DP(加强版)

    ID: 5500 远端评测题 3500ms 250MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>动态规划 DP线段树O2优化树链剖分动态树 LCT动态 DP全局平衡二叉树

【模板】动态 DP(加强版)

题目背景

树剖常数小!跑不满!

shadowice1984 为了向你证明他能卡树剖并且会卡树剖从而出了这道毒瘤题。

保证答案均在 int 范围内。

然后就被离线算法针对了……

因此这道题变成了强制在线。

题目描述

P4719

给定一个 nn 个点的带点权树,进行 mm 次修改点权的操作。

你需要在每次修改之后输出树上最大带权独立集的权值之和。

输入格式

P4719

第一行两个正整数 nnmm 表示树的点数和总操作个数

第二行 nn 个整数 V1,,VnV_1,\dots,V_n 表示每个点的点权。

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

接下来 mm 行每行两个整数 xxyy 表示将 xx 的点权修改为 yy

对于第 11 行,xx 即为被操作的点的编号。

对于第 22mm 行,被操作的点的编号 =xlastans=x\oplus lastans

其中 lastanslastans 是上一次操作后输出的答案,\oplus 表示按位异或操作。

输出格式

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

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

186
186
190
145
189
288
244
320
258
304

提示

数据范围 n1×106n \leq 1 \times 10^6m3×106m \leq 3 \times 10^6。保证任意时刻各点点权的绝对值 100\leq 100

时限为标程的二倍,如果卡常数的话请使用 int 类型。