A6656 | 「雅礼集训 2018 Day10」文明
时间限制2s
内存限制512MB
通过 / 提交0/0
题目描述
《文明》是一款流行的回合制策略游戏。游戏中玩家建立起一个帝国，并接受时间的考验。玩家将创建及带领自己的文明从石器时代迈向信息时代，并成为世界的领导者。在尝试建立起世界上赫赫有名的伟大文明的过程中，玩家将启动战争、实行外交、促进文化，同时正面对抗历史上的众多领袖。在游戏中，每个玩家都有一个属于自己的国家，随着时代更迭，国家的疆土也会越来越大，最后所有的国家将最终把整个游戏地图占领。
整个游戏地图是 $n$ 个结点的树，要在这个地图上进行 $q$ 次游戏，每次有 $k$ 个玩家，每个玩家的国家一开始的领土只有一个点 $a_1, a_2, ..., a_k$，保证每个点两两不同。然后 $1, 2, ..., k$ 号玩家轮流进行一个回合，每个回合可以对国家疆土上的所有节点进行距离为 $1$ 的扩展，如果扩展到不属于任何其他国家的节点，则将这个点划入自己国家的疆土。如此往复，直到所有的节点都被某个国家占领。
黈 (tǒu) 力最近沉迷于《文明》无法自拔，他想问问你他的国家能占领多大的游戏地图。由于黈力是 STEAM 上的黄金会员，所以他每次都是 $1$ 号玩家，即他每次都是第一个进行回合的。
整个游戏地图是 $n$ 个结点的树，要在这个地图上进行 $q$ 次游戏，每次有 $k$ 个玩家，每个玩家的国家一开始的领土只有一个点 $a_1, a_2, ..., a_k$，保证每个点两两不同。然后 $1, 2, ..., k$ 号玩家轮流进行一个回合，每个回合可以对国家疆土上的所有节点进行距离为 $1$ 的扩展，如果扩展到不属于任何其他国家的节点，则将这个点划入自己国家的疆土。如此往复，直到所有的节点都被某个国家占领。
黈 (tǒu) 力最近沉迷于《文明》无法自拔，他想问问你他的国家能占领多大的游戏地图。由于黈力是 STEAM 上的黄金会员，所以他每次都是 $1$ 号玩家，即他每次都是第一个进行回合的。
输入格式
第一行输入两个整数 $n, q$，分别表示游戏地图的节点数和游戏数。
接下来 $n - 1$ 行，每行输入两个整数 $x, y$，表示游戏地图中有连边 $x, y$，保证游戏地图是一棵无重边无自环的树。
接下来 $q$ 行，每行先输入一个整数 $k_i$，表示第 $i$ 局游戏有 $k_i$ 个玩家。
接下来 $k_i$ 个数 $a_{ij}$，表示这局游戏第 $j$ 个玩家的国家初始所在的节点。
接下来 $n - 1$ 行，每行输入两个整数 $x, y$，表示游戏地图中有连边 $x, y$，保证游戏地图是一棵无重边无自环的树。
接下来 $q$ 行，每行先输入一个整数 $k_i$，表示第 $i$ 局游戏有 $k_i$ 个玩家。
接下来 $k_i$ 个数 $a_{ij}$，表示这局游戏第 $j$ 个玩家的国家初始所在的节点。
输出格式
输出 $q$ 行 $q$ 个数，表示每次游戏黈力的国家能占领的节点数。
输入输出样例
输入 #1
6 4 1 2 1 3 2 4 3 5 3 6 2 1 3 3 1 4 5 3 4 5 6 3 1 2 3
输出 #1
3 4 3 1
| 测试点编号 | $n$ | $q$ | $k_i$ | 特殊情况 |
| :-: | :-: | :-: | :-: | :-: |
| 1 | $\leq 5$ | $\leq 5$ | | |
| 2 | $\leq 50$ | $\leq 50$ | | |
| 3 | $\leq 200$ | $\leq 200$ | | |
| 4 | $\leq 500$ | $\leq 500$ | | |
| 5 | $\leq 1500$ | $\leq 1500$ | | |
| 6 | $\leq 3000$ | $\leq 3000$ | | |
| 7 | $\leq 5000$ | $\leq 5000$ | | 游戏地图是一条链|
| 8 | $\leq 5000$ | $\leq 5000$ | | |
| 9 | | $\leq 10$ | $ = 2$ | |
| 10 | | $\leq 10$ | $\leq 10$ | |
| 11 | | $\leq 10$ | $\leq 5000$ | |
| 12 | | $\leq 10$ | | |
| 13 | $\leq 100000$ | $\leq 100000$ | $ = 2$ | |
| 14 | $\leq 250000$ | $\leq 250000$ | $ = 2$ | |
| 15 | | | $ = 2$ | |
| 16 | | | $ = 3$ | |
| 17 | | | $ \leq 10$ | |
| 18 | | | $ \leq 20$ | |
| 19 | $\leq 100000$ | $\leq 100000$ | |游戏地图是一条链 |
| 20 | | | |游戏地图是一条链 |
| 21 | $\leq 100000$ | $\leq 100000$ | |黈力永远在 $1$ 号点 |
| 22 | | | |黈力永远在 $1$ 号点 |
| 23 | | | | 树是随机的 |
| 24 | $\leq 250000$ | $\leq 250000$ | | |
| 25 | | | | | |
对于所有数据，有 $n, q \leq 500000, 1 \leq k_i \leq n, \sum_{i = 1}^{q} k_i \leq 1000000$。
| :-: | :-: | :-: | :-: | :-: |
| 1 | $\leq 5$ | $\leq 5$ | | |
| 2 | $\leq 50$ | $\leq 50$ | | |
| 3 | $\leq 200$ | $\leq 200$ | | |
| 4 | $\leq 500$ | $\leq 500$ | | |
| 5 | $\leq 1500$ | $\leq 1500$ | | |
| 6 | $\leq 3000$ | $\leq 3000$ | | |
| 7 | $\leq 5000$ | $\leq 5000$ | | 游戏地图是一条链|
| 8 | $\leq 5000$ | $\leq 5000$ | | |
| 9 | | $\leq 10$ | $ = 2$ | |
| 10 | | $\leq 10$ | $\leq 10$ | |
| 11 | | $\leq 10$ | $\leq 5000$ | |
| 12 | | $\leq 10$ | | |
| 13 | $\leq 100000$ | $\leq 100000$ | $ = 2$ | |
| 14 | $\leq 250000$ | $\leq 250000$ | $ = 2$ | |
| 15 | | | $ = 2$ | |
| 16 | | | $ = 3$ | |
| 17 | | | $ \leq 10$ | |
| 18 | | | $ \leq 20$ | |
| 19 | $\leq 100000$ | $\leq 100000$ | |游戏地图是一条链 |
| 20 | | | |游戏地图是一条链 |
| 21 | $\leq 100000$ | $\leq 100000$ | |黈力永远在 $1$ 号点 |
| 22 | | | |黈力永远在 $1$ 号点 |
| 23 | | | | 树是随机的 |
| 24 | $\leq 250000$ | $\leq 250000$ | | |
| 25 | | | | | |
对于所有数据，有 $n, q \leq 500000, 1 \leq k_i \leq n, \sum_{i = 1}^{q} k_i \leq 1000000$。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？