BZPRO

#5210. 最大连通子块和

内存限制：128 MiB 时间限制：20 Sec
提交 提交记录 讨论

题目描述

给出一棵n个点、以1为根的有根树，点有点权。要求支持如下两种操作：
M x y：将点x的点权改为y；
Q x：求以x为根的子树的最大连通子块和。
其中，一棵子树的最大连通子块和指的是：该子树所有子连通块的点权和中的最大值
（本题中子连通块包括空连通块，点权和为0）。

输入格式

第一行两个整数n、m，表示树的点数以及操作的数目。
第二行n个整数，第i个整数w_i表示第i个点的点权。
接下来的n-1行，每行两个整数x、y，表示x和y之间有一条边相连。
接下来的m行，每行输入一个操作，含义如题目所述。保证操作为M x y或Q x之一。
1≤n,m≤200000 ，任意时刻 |w_i|≤10^9 。

输出格式

对于每个Q操作输出一行一个整数，表示询问子树的最大连通子块和。

样例

样例输入


			
5 4

3 -2 0 3 -1

1 2

1 3

4 2

2 5

Q 1

M 4 1

Q 1

Q 2

样例输出


			
4

3

1

数据范围与提示

BZPRO Powered by Remmina.
Github Repository