Problem Description

百度科技园内有$n$个零食机，零食机之间通过$n-1$条路相互连通。每个零食机都有一个值$v$，表示为小度熊提供零食的价值。

由于零食被频繁的消耗和补充，零食机的价值$v$会时常发生变化。小度熊只能从编号为0的零食机出发，并且每个零食机至多经过一次。另外，小度熊会对某个零食机的零食有所偏爱，要求路线上必须有那个零食机。

为小度熊规划一个路线，使得路线上的价值总和最大。

Input

输入数据第一行是一个整数$T(T\leq 10)$，表示有$T$组测试数据。

对于每组数据，包含两个整数$n,m(1\leq n,m\leq 100000)$，表示有$n$个零食机，$m$次操作。

接下来$n-1$行，每行两个整数$x$和$y(0\leq x,y < n)$，表示编号为$x$的零食机与编号为$y$的零食机相连。

接下来一行由$n$个数组成，表示从编号为0到编号为$n-1$的零食机的初始价值$v(|v| < 100000)$。

接下来$m$行，有两种操作：$0\ x\ y$，表示编号为$x$的零食机的价值变为$y$；$1\ x$，表示询问从编号为0的零食机出发，必须经过编号为$x$零食机的路线中，价值总和的最大值。

本题可能栈溢出，辛苦同学们提交语言选择c++，并在代码的第一行加上：

`#pragma comment(linker, "/STACK:1024000000,1024000000") `

Output

对于每组数据，首先输出一行”Case #?:”，在问号处应填入当前数据的组数，组数从1开始计算。

对于每次询问，输出从编号为0的零食机出发，必须经过编号为$x$零食机的路线中，价值总和的最大值。

1
6 5
0 1
1 2
0 3
3 4
5 3
7 -5 100 20 -5 -7
1 1
1 3
0 2 -1
1 1
1 5

Case #1:
102
27
2
20