题目 1759

采访计划

查看题解 ↗GitHub ↗如何评测
题号
1759
时间限制
2000 ms
内存限制
128 MB
标签
数据结构
来源
信息学奥赛一本通 · 高手训练篇·四、数据结构(高手训练)

【题目描述】

公元2044年,人类将进入宇宙纪元。LL国有nn个星球,分别编号为11到nn,每一星球上有一个球长。因为历史的长期积淀,第i个星球上还有一位编号为i的德高望重的长者,因为长者德高望重,所以第ii个星球的球长一定被第i位长者管辖且长者管辖自己。每一位长者手里有一份名单BiB_i,上面记录着一些长者的编号。因为一些奥妙重重的原因,第ii位长者的名单上只可能有11至i−1i-1中的一些编号并且保证不会重复。因为长者都德高望重,所以第ii位长者管辖第jj位长者的充要条件是:对于每一个kk属于BiB_i,第kk位长者管辖第jj位长者。 此时,有一位记者想对一些球长进行采访,为了保证采访顺利,他决定先与一些长者搞好关系,以便采访被这些长者管辖的球长。为了与更多的球长谈笑风生,这位记者会给你提出mm个询问。第ii个询问中记者会给你fif_i个长者的编号,你需要回答有多少个星球的球长至少直接或间接被一位长者管辖。≤2000000$ 。

【输入】

第一行一个数nn,表示星球的个数。 接下来nn行,每一行描述一个BiB_i:首先给出BiB_i的大小szisz_i(可能为00),接下来szisz_i个数,描述BiB_i中的每一个元素。保证BiB_i中的数没有重复。 接下来一行,给出一个数mm,表示询问的个数。 接下来mm行,每一行描述一个询问:格式同上文对于集合BiB_i的格式。

【输出】

共m行,第i行输出第i次询问的答案。

【输入样例】

文本
7
0
1 1
1 1
1 2
2 2 3
0
2 2 6
3
2 2 3
2 3 5
2 4 5

【输出样例】

文本
3
3
4

【提示】

【样例解释】 对于第一个询问,2、32、3号长者都管辖11号长者,所以总共有33个球长可以被采访,编号分别为1,2,31,2,3。 对于第二个询问,3、53、5号长者都管辖11号长者,所以总共有33个球长可以被采访,编号分别为1,3,51,3,5。 对于第三个询问,44号长者管辖第1、21、2号长者,所以总共有44个球长可以被采访,编号分别为1,2,4,51,2,4,5。 特别说明:第55号长者没有管辖长者22,因为3∈B53∈B_5但22不属于B3B_3。但长者44管辖长者22,因为长者管辖自己。

题面图片 说明:图中省略了球长,编号代表长者有向边u→vu→v表示uu在BvB_v中

【数据规模及约定】 对于30%的数据,n,m≤100n,m≤100。 对于100%的数据,n,m≤200000,∑∣Bi∣≤2000000n,m≤200000,\sum|B_i|≤2000000 ,询问中的∑szi≤2000000\sum sz_i≤2000000 。

数据下载

题目 1759 的公开数据

正在读取文件列表…

常用命令

题目 1759 的 ROJ 命令

以下命令默认使用全局安装的 ROJ Skill,请在终端中直接执行;如果修改过 AGENT_HOME,请将命令中的 ~/.agents 替换为对应目录。