题目大意
链接 给定一棵树，每次给定一些点，求最少要阻断多少点使得这些点之间两两之间无法通行。其中不能阻断给定点，无解输出-1.
分析
虚树上贪心/DP即可。
虚树
由于在树上有可能有很多点根本就不需要用，所以我们要把这些点提出来单独组成一棵树，减少了大量运算。
一般来说我们要提出的点是所有的点和这些点之间两两LCA的点，然而K个点LCA的点仅仅有K-1个，也就是按照DFS序排序之后相邻的点之间LCA即可。
我挑了一种比较好理解和易于自己实现的写法。 首先获得原树，然后遍历之后得到DFS序，并且拥有一个办法求LCA，求出DFS序，求出每个点所在子树的时间戳范围。 对于每一组数据我们有如下操作：
获取结点，按照DFS序排序，相邻结点之间获取它们的LCA，再把所有结点按照DFS序排序，去重。弄一个栈，先加入DFS序最小的，它也就是整个虚树的根。依次加入结点，如果当前结点不在栈顶结点的子树内，就弹出栈顶结点。然后连接栈顶元素和当前元素，把当前元素入栈。
好了虚树就构建好了。
说几个注意的点：
建立虚树的时候是个有根树，可以不向根的方向连边，因此遍历的时候不用判断父亲结点。边和其它数据的还原最好利用我们得到的结点逐个还原，因为原树太大了。注意排序的时候要加cmp函数，但是unique的时候不要加。
代码
#include<cmath>
#include<queue>
#include<cctype>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=
3e5+
105,inf=
1e6,oo=
18;
int n,m;
int dfn,l[maxn],r[maxn],dep[maxn],fa[maxn][oo+
5];
struct Tree1
{
int np,first[maxn];
struct edge{
int to,next;
}E[maxn<<
1];
void add(
int u,
int v)
{
E[++np]=(edge){v,first[u]};
first[u]=np;
}
void DFS(
int i,
int f,
int d)
{
l[i]=++dfn;
dep[i]=d;
fa[i][
0]=f;
for(
int j=
1;j<=oo;j++)fa[i][j]=fa[fa[i][j-
1]][j-
1];
for(
int p=first[i];p;p=E[p].next)
{
int j=E[p].to;
if(j==f)
continue;
DFS(j,i,d+
1);
}
r[i]=dfn;
}
int LCA(
int u,
int v)
{
if(dep[u]<dep[v])swap(u,v);
int delt=(dep[u]-dep[v]);
for(
int j=
0;j<=oo;j++)
if((delt>>j)&
1)u=fa[u][j];
if(u==v)
return u;
for(
int j=oo;j>=
0;j--)
if(fa[u][j]!=fa[v][j])u=fa[u][j],v=fa[v][j];
return fa[u][
0];
}
void Init()
{
int u,v;
scanf(
"%d",&n);
for(
int i=
1;i<n;i++)
{
scanf(
"%d%d",&u,&v);
add(u,v);add(v,u);
}
DFS(
1,
0,
1);
scanf(
"%d\n",&m);
}
}tr;
int cnt,np,first[maxn],d[maxn],stk[maxn],top;
bool vis[maxn];
int sz[maxn],f[maxn];
struct edge{
int to,next;
}E[maxn<<
1];
void add(
int u,
int v)
{
E[++np]=(edge){v,first[u]};
first[u]=np;
}
bool cmp(
int x,
int y)
{
return l[x]<l[y];
}
void Build()
{
sort(d+
1,d+cnt+
1,cmp);
int to=cnt;
for(
int i=
1;i<to;i++)
d[++cnt]=tr.LCA(d[i],d[i+
1]);
sort(d+
1,d+cnt+
1,cmp);
cnt=unique(d+
1,d+cnt+
1)-d-
1;
top=
0;
stk[++top]=d[
1];
for(
int i=
2;i<=cnt;i++)
{
while(top && r[stk[top]]<l[d[i]])top--;
if(top)
add(stk[top],d[i]);
stk[++top]=d[i];
}
}
void dp(
int i)
{
f[i]=
0;
if(vis[i])
{
sz[i]=
1;
for(
int p=first[i];p;p=E[p].next)
{
int j=E[p].to;
dp(j);
f[i]+=f[j];
if(sz[j])f[i]++;
}
}
else
{
sz[i]=
0;
for(
int p=first[i];p;p=E[p].next)
{
int j=E[p].to;
dp(j);
f[i]+=f[j];
sz[i]+=sz[j];
}
if(sz[i]>
1)
{
sz[i]=
0;
f[i]++;
}
}
}
void query()
{
bool ok=
false;
scanf(
"%d",&cnt);
for(
int i=
1;i<=cnt;i++)
{
scanf(
"%d",&d[i]);
vis[d[i]]=
1;
}
for(
int i=
1;i<=cnt;i++)
if(vis[fa[d[i]][
0]])ok=
true;
if(ok)
printf(
"-1\n");
else
{
Build();
dp(d[
1]);
printf(
"%d\n",f[d[
1]]);
}
np=
0;
for(
int i=
1;i<=cnt;i++)
{
vis[d[i]]=
0;
first[d[i]]=
0;
}
}
int main()
{
tr.Init();
while(m--)
query();
return 0;
}
