Description：

给一棵树，每次询问给出 $k$ 个关键点，这些关键点不能破坏，问至少破坏几个点使得关键点两两不相连。

$1\leqslant n\leqslant 10^5$

Solution：

虚树是很显然的，然而树形 $DP$ 并没有那么显然，可以想到设一个 $f[k][0/1]$ 分别表示以 $k$ 为根的子树已经完全控制 $/$ 还有一个不受控制的最小代价，还是类似保安站岗那样的模型，如果是关键点，那么它的子树必须被完全控制，如果不是关键点，那么就分别求一个 $sum0$ 一个 $sum1$ ，在这个点放就是 $f[k][0]=sum1+1$ ，不放就是 $f[k][0]=sum0$ ，如果有一个延伸出去了，就找一个最小的 $sum0-f[son][0]+f[son][1]$ ，注意有一些细节就是每次要把 $f[k][1]$ 和 $f[k][0]$ 取 $min$ ，因为显然 $f[k][0]$ 限制更紧，还有就是如果两个点缩完后这条边在原树上还有其他点，那么可以破坏这些点。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,m;

#define MAXN 100010

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

int dep[MAXN],siz[MAXN],son[MAXN],top[MAXN],fa[MAXN];

int dfn[MAXN],tot = 0;

void dfs1(int k,int depth)

{

	dep[k] = depth;

	siz[k] = 1;

	dfn[k] = ++tot;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k])

		{

			fa[e[i].to] = k;

			dfs1(e[i].to,depth + 1);

			siz[k] += siz[e[i].to];

			if(son[k] == 0 || siz[e[i].to] > siz[son[k]])

			{

				son[k] = e[i].to;

			}

		}

	}

	return;

}

void dfs2(int k,int tp)

{

	top[k] = tp;

	if(son[k] == 0)return;

	dfs2(son[k],tp);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k] && e[i].to != son[k])

		{

			dfs2(e[i].to,e[i].to);

		}

	}

	return;

}

int LCA(int a,int b)

{

	while(top[a] != top[b])

	{

		if(dep[top[a]] < dep[top[b]])swap(a,b);

		a = fa[top[a]];

	}

	return (dep[a] < dep[b] ? a : b);

}

vector<int> g[MAXN];

int v[MAXN];

void ins(int f,int p)

{

	g[f].push_back(p);

	return;

}

int s[MAXN],tp;

bool tag[MAXN];

typedef long long ll;

#define INF 0x3f3f3f3f

ll f[MAXN][2];

void dp(int k)

{

	if(tag[k])

	{

		f[k][0] = INF;

		f[k][1] = 0;

		for(vector<int>::iterator i = g[k].begin();i != g[k].end();++i)

		{

			dp(*i);

			if(dep[*i] != dep[k] + 1)f[*i][0] = min(f[*i][0],f[*i][1] + 1);

			f[k][1] += f[*i][0];

		}

	}

	else

	{

		ll sum0 = 0,sum1 = 0;

		for(vector<int>::iterator i = g[k].begin();i != g[k].end();++i)

		{

			dp(*i);

			if(dep[*i] != dep[k] + 1)f[*i][0] = min(f[*i][0],f[*i][1] + 1);

			sum0 += f[*i][0];sum1 += f[*i][1];

		}

		f[k][0] = min(sum0,sum1 + 1);

		f[k][1] = INF;

		for(vector<int>::iterator i = g[k].begin();i != g[k].end();++i)

		{

			f[k][1] = min(f[k][1],sum0 - f[*i][0] + f[*i][1]);

		}

	}

	f[k][1] = min(f[k][1],f[k][0]);

	g[k].clear();

	return;

}

bool cmp_dfn(int a,int b){return dfn[a] < dfn[b];}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i < n;++i)add(rd(),rd());

	dfs1(1,1);dfs2(1,1);

	scanf("%d",&m);

	while(m--)

	{

		scanf("%d",&v[0]);

		for(int i = 1;i <= v[0];++i)v[i] = rd();

		for(int i = 1;i <= v[0];++i)tag[v[i]] = true;

		sort(v + 1,v + 1 + v[0],cmp_dfn);

		tp = 0;s[++tp] = v[1];

		for(int i = 2;i <= v[0];++i)

		{

			int lca = LCA(s[tp],v[i]);

			if(lca == s[tp])

			{

				s[++tp] = v[i];

				continue;

			}

			while(tp >= 2)

			{

				if(dfn[lca] < dfn[s[tp - 1]])

				{

					ins(s[tp - 1],s[tp]);

					--tp;

				}

				else

				{

					ins(lca,s[tp]);

					--tp;

					break;

				}

			}

			if(tp == 1 && dfn[lca] < dfn[s[tp]])

			{

				ins(lca,s[tp]);

				s[tp] = lca;

			}

			if(lca != s[tp])s[++tp] = lca;

			s[++tp] = v[i];

		}

		while(tp >= 2)

		{

			ins(s[tp - 1],s[tp]);

			--tp;

		}

		dp(s[tp]);

		ll ans = min(f[s[tp]][0],f[s[tp]][1]);

		if(ans == INF)ans = -1;

		printf("%lld\n",ans);

		for(int i = 1;i <= v[0];++i)tag[v[i]] = false;

	}

	return 0;

}