[Contest #8]黄金体验

内存限制：256 MB 时间限制：1000 ms

给出一颗有 $n$ 个节点的树，每个点有一个初始权值 $w_i$，要求支持两种操作

1.给出 $x$，$y$，使点 $x$ 的权值增加 $y$。

2.给出 $k$，选定 $k$ 个点使得包含这 $k$ 个点的最小联通子图点权和最大，你只需要输出这个最大值。

第一行包含一个数 $n$ 表示树的节点数。

之后 $n-1$ 行每行包含两个整数 $u, v$，表示树上 $u, v$ 两点间存在一条边。

接下来一行包含 $n$ 个整数 $w_i$，表示每个点的初始权值。

接下来一行包含一个整数 $q$ 表示操作数。

接下来 $q$ 行每行先输入一个整数 $ty$,

如果 $ty=0$ 表示一组修改，之后读入两个整数 $x,y$ 表示使点 $x$ 的点权增加$y$。

如果 $ty=1$ 表示一组询问，之后读入一个整数 $k$ 意义如题面中所述。

$1\leq x,\ k\leq n\leq10^5$
$q\leq 10^5$
$0\leq ty\leq1$
$0\leq w_i,y \leq 10^9$

对于每一组询问输出一个整数表示答案。

样例输入 1

样例输出 1

8
10
13

样例输入 2

8
1 2
1 4
1 8
2 3
4 5
4 6
4 7
1 1 1 1 1 1 1 1
6
1 2
0 8 1
1 3
0 7 2
1 3
1 2

样例输出 2