题目名称 2383. [HNOI 2014]世界树
输入输出 worldtree.in/out
难度等级 ★★★★
时间限制 2000 ms (2 s)
内存限制 512 MiB
测试数据 10
题目来源 GravatarTenderRun 于2016-07-11加入
开放分组 全部用户
提交状态
分类标签
分享题解
通过:27, 提交:63, 通过率:42.86%
Gravataronlysky 100 0.944 s 27.21 MiB C++
Gravatar小一米 100 1.071 s 48.29 MiB C++
GravatarGintoki 100 1.128 s 54.46 MiB C++
Gravatarlyqlyqcogs 100 1.227 s 24.32 MiB C++
Gravatar神利·代目 100 1.292 s 24.32 MiB C++
Gravatarassassain 100 1.353 s 24.32 MiB C++
GravatarSteven 100 1.520 s 42.64 MiB C++
GravatarHermera 100 1.648 s 41.49 MiB C++
GravatarHermera 100 1.664 s 41.49 MiB C++
Gravatarasd 100 1.696 s 46.09 MiB C++
关于 世界树 的近10条评论(全部评论)
回复 @FoolMike :
%%%
GravatarNew World
2017-02-14 20:26 6楼
我写的虚树还是挺快的哈,似乎用堆造虚树也是挺快的嘛
GravatarFoolMike
2017-02-14 20:26 5楼
^_^
GravatarTenderRun
2016-08-27 10:07 4楼
Gravatar神利·代目
2016-07-15 09:24 3楼
回复 @安吶。 :
VIP
好能联想,那你看到电磁炮不会猛戳进去了吧
Gravatarsvideo
2016-07-11 09:25 2楼
还以为是刀剑里面精灵世界的世界树 直接戳进来了
Gravatar安呐一条小咸鱼。
2016-07-11 08:23 1楼

2383. [HNOI 2014]世界树

★★★★   输入文件:worldtree.in   输出文件:worldtree.out   简单对比
时间限制:2 s   内存限制:512 MiB

【题目描述】

世界树是一棵无比巨大的树,它伸出的枝干构成了整个世界。在这里,生存着各种各样的种族和生灵,他们共同信奉着绝对公正公平的女神艾莉森,在他们的信条里,公平是使世界树能够生生不息、持续运转的根本基石。
世界树的形态可以用一个数学模型来描述:世界树中有n个种族,种族的编号分别从1到n,分别生活在编号为1到n的聚居地上,种族的编号与其聚居地的编号相同。有的聚居地之间有双向的道路相连,道路的长度为1。保证连接的方式会形成一棵树结构,即所有的聚居地之间可以互相到达,并且不会出现环。定义两个聚居地之间的距离为连接他们的道路的长度;例如,若聚居地a和b之间有道路,b和c之间有道路,因为每条道路长度为1而且又不可能出现环,所以a与c之间的距离为2。
出于对公平的考虑,第i年,世界树的国王需要授权m[i]个种族的聚居地为临时议事处。对于某个种族x(x为种族的编号),如果距离该种族最近的临时议事处为y(y为议事处所在聚居地的编号),则种族x将接受y议事处的管辖(如果有多个临时议事处到该聚居地的距离一样,则y为其中编号最小的临时议事处)。
现在国王想知道,在q年的时间里,每一年完成授权后,当年每个临时议事处将会管理多少个种族(议事处所在的聚居地也将接受该议事处管理)。 现在这个任务交给了以智慧著称的灵长类的你:程序猿。请帮国王完成这个任务吧。

【输入格式】

第一行为一个正整数n,表示世界树中种族的个数。
接下来n-l行,每行两个正整数x,y,表示x聚居地与y聚居地之间有一条长度为1的双
向道路。接下来一行为一个正整数q,表示国王询问的年数。
接下来q块,每块两行:
第i块的第一行为1个正整数m[i],表示第i年授权的临时议事处的个数。
第i块的第二行为m[i]个正整数h[l]、h[2]、…、h[m[i]],表示被授权为临时议事处的聚居地编号(保证互不相同)。

【输出格式】

输出包含q行,第i行为m[i]个整数,该行的第j(j=1,2…,,m[i])个数表示第i年被授权的聚居地h[j]的临时议事处管理的种族个数。

【样例输入】

10 
2 1 
3 2 
4 3 
5 4 
6 1 
7 3 
8 3 
9 4 
10 1 
5 
2 
6 1   
5 
2 7 3 6 9   
1 
8  
4 
8 7 10 3   
5 
2 9 3 5 8 

【样例输出】

1 9   
3 1 4 1 1   
10  
1 1 3 5   
4 1 3 1 1 

【提示】


N<=300000, q<=300000,m[1]+m[2]+…+m[q]<=300000