4836：The Query on the Tree

题目描述

　　度度熊最近沉迷在和树有关的游戏了，他一直认为树是最神奇的数据结构。一天他遇到这样一个问题：
　　有一棵树，树的每个点有点权，每次有三种操作：
　　1. Query x 表示查询以x为根的子树的权值和。
　　2. Change x y 表示把x点的权值改为y(0<=y<=100)。
　　3. Root x 表示把x变为根。
　　现在度度熊想请更聪明的你帮助解决这个问题。

输入解释

　　第一行为数据组数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行为描述中的三种操作。

输出解释

　　对于第k组输入数据，第一行输出Case #k 接下来对于每个”Query x”操作，输出以x为根的子数和。

输入样例

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

输出样例

Case #1:
15
22
18
Case #2:
36 
33
6
3

来自杭电HDUOJ的附加信息

Recommend

liuyiding

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 2014年百度之星程序设计大赛 - 复赛

源链接： HDU-4836

最后修改于 2020-10-25T23:17:18+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
2000/1000MS(Java/Others)	32768/32768K(Java/Others)