分析
若两个重要城市为一条边的两个顶点显然无解
否则考虑建一棵虚树，设(dp[x])表示以(x)为根的子树最少需要摧毁的城市数，
令(Siz[x])表示(x)有多少个子节点需要被摧毁，
若(x)这个点是一个重要城市，则(dp[x]+=Siz[x],Siz[x]=1)
即表示(x)所有需要被摧毁的子节点必须摧毁
否则如果多于1个子节点需要被摧毁，那么毁掉(x)这座非重要城市
当然(dp[x])要计算子节点的答案
代码
#include <cstdio>
#include <cctype>
#include <algorithm>
#define rr register
using namespace std;
const int N=100011; struct node{int y,next;}e[N<<1],E[N]; int stac[N],hs[N],a[N];
int dep[N],fat[N],siz[N],as[N],Siz[N],big[N],dfn[N],tot,Top[N],n,et=1,Et,m,dp[N],F,v[N];
inline signed iut(){
rr int ans=0; rr char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
inline void dfs1(int x,int fa){
dep[x]=dep[fa]+1,fat[x]=fa,siz[x]=1;
for (rr int i=as[x],SIZ=-1;i;i=e[i].next)
if (e[i].y!=fa){
dfs1(e[i].y,x),siz[x]+=siz[e[i].y];
if (SIZ<siz[e[i].y]) big[x]=e[i].y,SIZ=siz[e[i].y];
}
}
inline void dfs2(int x,int linp){
dfn[x]=++tot,Top[x]=linp;
if (!big[x]) return; dfs2(big[x],linp);
for (rr int i=as[x];i;i=e[i].next)
if (e[i].y!=big[x]&&e[i].y!=fat[x])
dfs2(e[i].y,e[i].y);
}
inline signed lca(int x,int y){
while (Top[x]^Top[y]){
if (dep[Top[x]]<dep[Top[y]]) x^=y,y^=x,x^=y;
x=fat[Top[x]];
}
if (dep[x]>dep[y]) x^=y,y^=x,x^=y;
return x;
}
inline bool cmp(int x,int y){return dfn[x]<dfn[y];}
inline void add(int x,int y){E[++Et]=(node){y,hs[x]},hs[x]=Et;}
inline void Insert(int x){
if (!tot) {stac[++tot]=x; return;}
rr int Lca=lca(x,stac[tot]);
while (tot>1&&dep[Lca]<dep[stac[tot-1]]) add(stac[tot-1],stac[tot]),--tot;
if (dep[Lca]<dep[stac[tot]]) add(Lca,stac[tot]),--tot;
if (stac[tot]!=Lca) stac[++tot]=Lca; stac[++tot]=x;
}
inline void dfs(int x){
dp[x]=Siz[x]=0;
for (rr int i=hs[x];i;i=E[i].next)
dfs(E[i].y),dp[x]+=dp[E[i].y],Siz[x]+=Siz[E[i].y];
hs[x]=0;
if (v[x]) dp[x]+=Siz[x],Siz[x]=1;
else if (Siz[x]>1) ++dp[x],Siz[x]=0;
}
signed main(){
n=iut();
for (rr int i=1;i<n;++i){
rr int x=iut(),y=iut();
e[++et]=(node){y,as[x]},as[x]=et;
e[++et]=(node){x,as[y]},as[y]=et;
}
dfs1(1,0),dfs2(1,1);
for (rr int Q=iut();Q;--Q){
m=iut(),tot=Et=F=0,a[++m]=1;
for (rr int i=1;i<m;++i) v[a[i]=iut()]=1;
for (rr int i=1;i<m;++i)
if (v[fat[a[i]]]){
printf("-1
");
F=1;
break;
}
if (!F){
sort(a+1,a+1+m,cmp),m=unique(a+1,a+1+m)-a-1;
for (rr int i=1;i<=m;++i) Insert(a[i]);
for (;tot>1;--tot) add(stac[tot-1],stac[tot]);
dfs(1);
printf("%d
",dp[1]);
}
for (rr int i=1;i<=m;++i) v[a[i]]=0;
}
return 0;
}