• 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。