• Tree

 

 

时间限制:1s

空间限制:512MB

 

题目描述

 

给定一棵无根树,第i个节点的权值为v_i,要求支持两个操作:

1、将节点x的权值v_x修改为y;

2、选择一个连通块(0个节点也可以),使得这个连通块包含的点点权和最大。

 

输入格式

 

第一行两个整数n,m。

第二行n个整数,第i个整数表示节点i的初始权值v_i。

接下来n-1行,每行两个整数x_i,y_i,描述树的一条边(x_i,y_i)。

接下来m行,每行描述一个操作:

1、如果格式为1 x y,则表示将节点x的权值v_x修改为y;

2、如果格式为2,则表示一个询问操作,求出点权和最大的连通块的点权和。

 

输出格式

 

对于每个询问操作,输出得到的点权和。

 

样例输入

 

5 7

2 -1 -3 1 1

1 2

1 3

3 4

3 5

2

1 3 0

2

1 2 1

2

1 1 -3

2

 

样例输出

 

2

4

5

2

 

数据范围

 

对于30%的数据,1<=n,m<=1,000。

对于另外20%的数据,1<=n,m<=100,000,树形态为一条链。

对于100%的数据,1<=n,m<=100,000,任何时刻|v_i|<=1,000。