题目链接：http://codeforces.com/contest/613/problem/D
题意概述：
给出一棵树，每次询问一些点，计算最少删除几个点可以让询问的点两两不连通，无解输出-1。保证询问的点总数不大于300000。
分析：
先考虑遍历的做法，统计每个点代表的子树中联通询问点的数量。
这个点不是询问点：如果有至少两个不同的子树中有询问点那么当前点一定被删除，因为这个时候不删除之后这两个点就是联通的；同时除了在更深的地方遇见第一种情况之外没有必要删除那些点；没有点不用管，只有一个点返回1。
这个点是询问点：每有一颗子树中有儿子就删除掉一个点。
判断无解：树上两个相邻的点都是询问点。
然后建立虚树在上面跑这个算法就可以了，减少无谓遍历的点的数量。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<cctype>
using namespace std;
const int maxn=; int N,Q;
struct edge{ int to,next; }E[maxn<<];
int first[maxn],np,fa[maxn][],dep[maxn],s[maxn],s_top;
int dfn[maxn],dfs_clock,stk[maxn],top,use[maxn],u_top;
bool inq[maxn];
struct vTree{
static const int maxnode=;
int first[maxnode],np,ans; bool vis[maxnode];
edge E[maxnode<<];
vTree(){
memset(first,,sizeof(first));
np=ans=;
memset(vis,,sizeof(vis));
}
void add_edge(int u,int v){
E[++np]=(edge){v,first[u]};
first[u]=np;
}
int DFS(int i,int f){
int cnt=;
for(int p=first[i];p;p=E[p].next){
int j=E[p].to;
if(j==f) continue;
if(DFS(j,i)){
if(vis[i]) ans++;
else cnt++;
}
}
if(vis[i]) return ;
if(cnt>){ ans++; return ; }
return cnt;
}
}vt; void _scanf(int &x)
{
x=;
char ch=getchar();
while(ch<''||ch>'') ch=getchar();
while(ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
}
int out_cnt; char out[];
void _printf(int x)
{
if(x<) putchar('-'),x=-x;
out[++out_cnt]=x%+'',x/=;
while(x) out[++out_cnt]=x%+'',x/=;
while(out_cnt) putchar(out[out_cnt--]);
putchar('\n');
}
void add_edge(int u,int v)
{
E[++np]=(edge){v,first[u]};
first[u]=np;
}
void data_in()
{
_scanf(N);
int x,y;
for(int i=;i<N;i++){
_scanf(x);_scanf(y);
add_edge(x,y); add_edge(y,x);
}
_scanf(Q);
}
void ready(int i,int f,int d)
{
fa[i][]=f,dep[i]=d,dfn[i]=++dfs_clock;
for(int j=;(<<j)<d;j++)
fa[i][j]=fa[fa[i][j-]][j-];
for(int p=first[i];p;p=E[p].next){
if(E[p].to==f) continue;
ready(E[p].to,i,d+);
}
}
int LCA(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
int len=dep[x]-dep[y];
for(int i=;(<<i)<=len;i++)
if((<<i)&len) x=fa[x][i];
if(x==y) return x;
for(int i=;i>=;i--)
if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][];
}
bool cmp(int x,int y) { return dfn[x]<dfn[y]; }
void build_vt()
{
stk[++top]=,inq[]=,use[++u_top]=;
if(s[]!=) stk[++top]=s[],inq[s[]]=,use[++u_top]=s[];
for(int j=;j<=s_top;j++){
int z=LCA(s[j],s[j-]);
while(top>&&dep[stk[top-]]>dep[z]){
vt.add_edge(stk[top-],stk[top]);
vt.add_edge(stk[top],stk[top-]);
top--;
}
if(top&&dep[stk[top]]>dep[z]){
vt.add_edge(stk[top],z);
vt.add_edge(z,stk[top]);
top--;
}
if(!inq[z]) inq[z]=,stk[++top]=z,use[++u_top]=z;
if(!inq[s[j]]) inq[s[j]]=,stk[++top]=s[j],use[++u_top]=s[j];
}
while(top>){
vt.add_edge(stk[top-],stk[top]);
vt.add_edge(stk[top],stk[top-]);
top--;
}
top=;
}
void work()
{
ready(,,);
int k,x;
for(int i=;i<=Q;i++){
_scanf(k);
for(int j=;j<=k;j++){
_scanf(x);
s[++s_top]=x,vt.vis[x]=;
}
bool ok=;
for(int j=;j<=s_top;j++)
if(vt.vis[fa[s[j]][]]){ ok=; break; }
if(!ok) _printf(-);
else{
sort(s+,s+s_top+,cmp);
build_vt();
vt.DFS(,);
_printf(vt.ans);
}
while(s_top) vt.vis[s[s_top--]]=;
while(u_top) inq[use[u_top]]=,vt.first[use[u_top]]=,u_top--;
vt.np=vt.ans=;
}
}
int main()
{
data_in();
work();
return ;
}