UOJ Logo

NOI.AC

1S 512MB

#121. 纲举目张

统计

纲举目张

输入一棵n个点的树,每条边的长度是1,

一共q次询问,每次询问k个点,

B君希望在树上保留最少的边,使得询问给出的k个点是连通的。

输出最小的边数。

输入描述

第一行一个整数n。

接下来n-1行,每行两个整数x, y表示一条边,点标号从1开始。

接下来一行一个整数q。

接下来q行,每行一个询问,第一个整数表示k,接下来k个整数表示询问的点。

输出描述

对于每个询问,输出一个整数,表示最少保留多少条边。

样例输入

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

样例输出

2
4
3

数据规模与约定

对于100%的数据,满足$1 <= n <= 1e5, 1 <= q <= 1e5, 2 <= k <= 4$

对于40%的数据,满足$k <= 2$

对于80%的数据,满足$k <= 3$

对于以上每部分,都有50%的数据满足$n <= 1e3$