#6514. 「雅礼集训 2018 Day10」文明

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

《文明》是一款流行的回合制策略游戏。游戏中玩家建立起一个帝国,并接受时间的考验。玩家将创建及带领自己的文明从石器时代迈向信息时代,并成为世界的领导者。在尝试建立起世界上赫赫有名的伟大文明的过程中,玩家将启动战争、实行外交、促进文化,同时正面对抗历史上的众多领袖。在游戏中,每个玩家都有一个属于自己的国家,随着时代更迭,国家的疆土也会越来越大,最后所有的国家将最终把整个游戏地图占领。

整个游戏地图是 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 个玩家的国家初始所在的节点。

输出格式

输出 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

样例解释 1

第一局游戏黈力一开始在 1 号点,第一时刻占领了 2 号点,第二时刻占领了 4 号点。

第二局游戏黈力一开始在 1 号点,第一时刻占领了 2 号点和 3 号点,第二时刻占领了 6 号点。

第四局游戏黈力一开始在 1 号点,然后没有其他可以占领的点。

数据范围与提示

测试点编号 n q k_i 特殊情况
1 \leq 5
2 \leq 50
3 \leq 200
4 \leq 500
5 \leq 1500
6 \leq 3000
7 \leq 5000 游戏地图是一条链
8
9 \leq 10 = 2
10 \leq 10
11 \leq 5000
12
13 \leq 100000 = 2
14 \leq 250000
15
16 = 3
17 \leq 10
18 \leq 20
19 \leq 100000 游戏地图是一条链
20
21 \leq 100000 黈力永远在 1 号点
22
23 树是随机的
24 \leq 250000
25

对于所有数据,有 n, q \leq 500000, 1 \leq k_i \leq n, \sum_{i = 1}^{q} k_i \leq 1000000