F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Problem 5210. -- 最大连通子块和

5210: 最大连通子块和

Time Limit: 20 Sec  Memory Limit: 128 MB
Submit: 746  Solved: 210
[Submit][Status][Discuss]

Description

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

Input

第一行两个整数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 。

Output

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

Sample Input

5 4
3 -2 0 3 -1
1 2
1 3
4 2
2 5
Q 1
M 4 1
Q 1
Q 2

Sample Output

4
3
1

HINT

Source

CQzhangyu&GXZlegend原创,本OJ版权所有,翻版必究

[Submit][Status][Discuss]

HOME Back