$\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$ |