Snacks

Time Limit: 10000/5000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

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$零食机的路线中,价值总和的最大值。

Sample Input

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

Sample Output

Case #1: 102 27 2 20

Hint

wange2014

Source

2016"百度之星" - 初赛(Astar Round2A)

提交代码