MMSet2
题号:NC14250
时间限制:C/C++/Rust/Pascal 3秒,其他语言6秒
空间限制:C/C++/Rust/Pascal 128 M,其他语言256 M
64bit IO Format: %lld

题目描述

给定一棵n个节点的树,点编号为1…n。
Q次询问,每次询问给定一个点集S,令f(u)=\max_{v\in S} dist(u,v)
你需要求出\min_{u=1...n}f(u)
其中dist(u,v)表示树上路径(u,v)的边数。

输入描述:

第一行一个整数n,接下来n−1行每行两个整数表示树上的一条边。
接下来一行一个整数Q,接着Q行,每行第一个数是|S|,剩下|S|个互不相同的数代表这个集合。

输出描述:

输出Q行,每行一个整数表示答案。
示例1

输入

复制
3
1 2
1 3
1
2 2 3

输出

复制
1

备注:

n≤3×105,|S|≥1,∑|S|≤106