#2284. 世界树

    ID: 2284 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>PROV赛事:contest2459来源:qoj.ac数据:公开样例广搜并查集

世界树

世界树

题目描述

第3 页,共7 页 

第2 题:世界树(worldtree),运行时限2s,内存上限512M,100 分。 【问题描述】

世界树是一棵无比巨大的树,它伸出的枝干构成了整个世界。在这里,生存着各种各样的 种族和生灵,他们共同信奉着绝对公正公平的女神艾莉森,在他们的信条里,公平是使世界树 能够生生不息、持续运转的根本基石。

世界树的形态可以用一个数学模型来描述: 世界树中有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 年的时间里,每一年完成授权后,当年每个临时议事处将会管理多 少个种族(议事处所在的聚居地也将接受该议事处管理)。 现在这个任务交给了以智慧著称的灵长类的你:程序猿。请帮国王完成这个任务吧。 【输入格式】

输入文件名为worldtree.in。

第一行为一个正整数n,表示世界树中种族的个数。

接下来n-1 行,每行两个正整数x,y,表示x 聚居地与y 聚居地之间有一条长度为1 的双 向道路。

接下来一行为一个正整数q,表示国王询问的年数。

接下来q 块,每块两行: 第i 块的第一行为1 个正整数m[i],表示第i 年授权的临时议事处的个数。 第i 块的第二行为m[i]个正整数h[1]、h[2]、…、h[m[i]],表示被授权为临时议事处 的聚居地编号(保证互不相同)。 【输出格式】

2014‐05‐10  第4 页,共7 页  输出文件名为worldtree.out。 输出包含q 行,第i 行为m[i]个整数,该行的第j(j=1,2,…,m[i])个数表示第i 年被授权 的聚居地h[j]的临时议事处管理的种族个数。 【输入输出样例】 worldtree.in worldtree.out 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 【样例解释】 树结构如图所示:

对于第二年的询问:

2014‐05‐10 

询问:2,7,3,6,9 他们分别管辖的顶点个数为:3,1,4,1,1(被同一点管辖的点染上了相同的颜色)。 【数据范围】

对于30%的数据满足n≤1000, q≤1000, m[1]+m[2]+…+m[q] ≤10000; 对于60%的数据满足n≤100000, q≤100000, m[1]+m[2]+…+m[q]≤100000; 对于100%的数据满足n≤300000, q≤300000, m[1]+m[2]+…+m[q] ≤300000。 【编译命令】

对于c++语言: g++ -o worldtree worldtree.cpp –lm 对于c语言: gcc -o worldtree worldtree.c –lm 对于pascal语言: fpc worldtree.pas

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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