Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:1024 MB
统计

$\color{red}问题描述$

出题人有一颗 $n$ 个结点的树。其中 $k$ 个结点上着了火。

每过 $1$ 单位的时间,一个结点上的火势就会蔓延到与它相邻的结点上,现在你需要求出整棵树着火(即全部结点上失火)的最小时间。

$Q$ 组询问,每组询问给出一个整数 $k$ 和 $k$ 个着火的结点。

$\color{orange}输入格式$

第一行两个正整数 $n,Q$ 表示结点数和询问数。

接下来 $n-1$ 行,每行两个正整数表示一条树边,树上结点标号从 $1$ 开始。

接下来 $Q$ 行,每行如以下格式输入:

第一行一个整数 $K$,表示该组询问中着火结点的个数; 第二行 $K$ 个整数 $a_i$,表示着火结点的编号。

$\color{yellow}输出格式$

输出共 $Q$ 行,第 $i$ 行表示第 $i$ 组询问中整棵树着火的最小时间。

$\color{green}样例输入输出$

5 2 
3 1 
2 1 
2 4 
2 5 
1
5
4
5 4 1 3
3
1

$\color{blue}数据范围$

令 $m=\sum\limits_{i=1}^QK_i$。

对于所有数据,有 :

$1\le n,m\le 10^5$

子任务编号 $ ~~~~~~~n,m~~~~~~~$ 特殊性质$ ~~~~~~~~~$ 分值
$1$ $\le 100$ $10$
$2$ $\le 2000$ $10$
$3$ $\le 10^5$ 保证树是一条链 $5$
$4$ $\le 10^5$ 保证询问次数 $Q\le 10$ $5$
$5$ $\le 10^5$ 保证每次询问 $K\le 2$ $15$
$5$ $\le 10^5$ 保证每次询问 $K\le 10$ $5$
$7$ $\le 10^5$ $50$