Problem Description
度度熊最近沉迷在和树有关的游戏了,他一直认为树是最神奇的数据结构。一天他遇到这样一个问题:
有一棵树,树的每个点有点权,每次有三种操作:
1. Query x 表示查询以x为根的子树的权值和。
2. Change x y 表示把x点的权值改为y(0<=y<=100)。
3. Root x 表示把x变为根。
现在度度熊想请更聪明的你帮助解决这个问题。
Input
第一行为数据组数T(1 <= T <= 100)
每组数据第一行为N(1<= N <= 10000),表示树的节点数。
后面N-1行每行有两个数x,y ,表示x,y之间有一条边 1<=x,y<=N。初始时树是以1号节点为根节点。
之后的一行为N个数表示这N个点的点权(点权的范围是0到100)。
然后为整数Q(Q<=1000)为操作次数。
之后的Q行为描述中的三种操作。
Output
对于第k组输入数据,第一行输出Case #k 接下来对于每个”Query x”操作,输出以x为根的子数和。
Sample Input
2
5
1 2
1 3
3 4
3 5
1 2 3 4 5
5
Query 1
Change 3 10
Query 1
Root 4
Query 3
8
1 2
1 3
3 4
4 5
5 6
5 7
4 8
1 2 3 4 5 6 7 8
5
Query 1
Query 3
Root 5
Query 3
Query 1
Sample Output
Case #1:
15
22
18
Case #2:
36
33
6
3