2608. [河南省队2016]无根树

【题目描述】

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

*将节点x的权值v_x修改为y

*选择一个连通块（0个节点也可以），使得这个连通块包含的点点权和最大

【输入格式】

第一行两个整数n,m。

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

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

接下来m行，每行描述一个操作：

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

*如果格式为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 <= 10^3。

对于另外20%的数据，1 <= n,m <= 10^5，树形态为一条链。

对于100%的数据，1 <= n,m <= 10^5，|v_i| <= 1000。

【来源】

2016河南省队集训，数据是Mike造的，如果数据有误请联系Mike，谁有官测直接刷掉就好。