#6184. 无心行挽

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

题目描述

不必做好输掉一切的准备。
所以,无畏结局。
在尽头,已经不能再做什么,来挽回。
在尽头,所有的一切都走向简化,没有了重复,没有了错杂,只剩下一片废墟。
就是说,世界曾是一副错杂的无向图,而在尽头,它已成为一个没有环的无向连通图,也就是说已成为一棵树。
这棵树有 n 个节点,有 n-1 条边,每条边的长度都是 1
给出 q 组询问,每组询问会给出 k 个关键点,设 f(u) 表示所有关键点中离点 u 最近的关键点离 u 的距离,求出最大的 f(u)

输入格式

第一行两个正整数 n q 表示树的节点个数以及询问个数。
接下来 n-1 行每行三个数 u,v 描述一条边,表示 u v 之间有一条长度为 1 的无向边。
接下来 q 组询问,每组询问第一行一个正整数 k 表示这组询问中关键点的个数,第二行 k 个正整数,表示这组询问的 k 个关键点。

输出格式

q 行,第 i 行对于第 i 组询问给出答案,详情见题目描述。

样例

样例输入 1

7 5
5 4
6 5
7 3
7 4
1 5
2 4
1
4
1
6
4
6 5 7 2
5
1 5 4 3 7
2
2 3

样例输出 1

2
4
1
1
3

样例输入 2, 3

见附加文件

样例输出 2, 3

见附加文件

数据范围与提示

S 表示所有询问里 k 的和。
对于 20\% 的数据, 1 \leq n,q,S \leq 3000
对于另外 30\% 的数据,每组询问的 k \leq 5
对于另外 10\% 的数据,给出的树是一条链。
对于另外 20\% 的数据, 1 \leq q \leq 10
对于 100\% 的数据, 1 \leq n,q,S \leq 100000

鸣谢 Samjia 和大树与 Samjia 和矩阵的题面主角 Samjia2000 授权本 OJ 独家拥有在线测评使用权。