Best Coder ^beta
VIP | STD Contests
DIY | Web-DIY ^beta

The Query on the Tree

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 470 Accepted Submission(s): 232

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

Source

2014年百度之星程序设计大赛 - 复赛

Statistic | Submit | Discuss | Note

Home | Top

Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-11-22 09:27:39, Gzip enabled

Administration