Description
一个王国有n座城市，城市之间由n-1条道路相连，形成一个树结构，国王决定将一些城市设为重要城市。
这个国家有的时候会遭受外敌入侵，重要城市由于加强了防护，一定不会被占领。而非重要城市一旦被占领，这座城市就不能通行。
国王定了若干选择重要城市的计划，他想知道，对于每个计划，外敌至少要占领多少个非重要城市，才会导致重要城市之间两两不连通。如果外敌无论如何都不可能导致这种局面，输出-1
Input
第一行$n$。
后面$n-1$行给出树边
再一行$m$，后面给出$m$组询问，
一组询问给定一个数$k$，同时$k$后面跟着$k$个整数。
Output
一行答案。
Sample Input1
4
1 3
2 3
4 3
4
2 1 2
3 2 3 4
3 1 2 4
4 1 2 3 4
1 3
2 3
4 3
4
2 1 2
3 2 3 4
3 1 2 4
4 1 2 3 4
Sample Output1
1
-1
1
-1
-1
1
-1
Sample Input2
7
1 2
2 3
3 4
1 5
5 6
5 7
1
4 2 4 6 7
1 2
2 3
3 4
1 5
5 6
5 7
1
4 2 4 6 7
Sample Output2
2
Solution
$LCA$写错身败名裂了啊QAQ……
先建个虚树，然后特判掉无解，也就是有两个关键点相邻的情况。
判完无解后$DP$，设$F[i]$表示解决$i$子树的最小花费，$G[i]$表示$i$子树中还没有被阻断的点数。
具体转移看代码吧，也挺好懂的……
Code
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>
#define N (100009)
using namespace std; struct Edge{int to,next;}edge[N<<];
int n,u,v,m,k,dfs_num,flag;
int a[N],DFN[N],Depth[N],f[N][],vis[N],F[N],G[N];
int head[N],num_edge; void add(int u,int v)
{
edge[++num_edge].to=v;
edge[num_edge].next=head[u];
head[u]=num_edge;
} void DFS(int x,int fa)
{
f[x][]=fa;
for (int i=; i<=; ++i)
f[x][i]=f[f[x][i-]][i-];
DFN[x]=++dfs_num; Depth[x]=Depth[fa]+;
for (int i=head[x]; i; i=edge[i].next)
if (edge[i].to!=fa) DFS(edge[i].to,x);
} int LCA(int x,int y)
{
if (Depth[x]<Depth[y]) swap(x,y);
for (int i=; i>=; --i)
if (Depth[f[x][i]]>=Depth[y]) x=f[x][i];
if (x==y) return x;
for (int i=; i>=; --i)
if (f[x][i]!=f[y][i]) x=f[x][i], y=f[y][i];
return f[x][];
} struct E{int to,next;}EDGE[N<<];
int HEAD[N],NUM_EDGE;
int stack[N],top;
bool cmp(int u,int v) {return DFN[u]<DFN[v];} void ADD(int u,int v)
{
if (u==v) return;
EDGE[++NUM_EDGE].to=v;
EDGE[NUM_EDGE].next=HEAD[u];
HEAD[u]=NUM_EDGE;
} void Insert(int x)
{
if (top==) {stack[++top]=x; return;}
int lca=LCA(x,stack[top]);
if (lca==stack[top]) {stack[++top]=x; return;}
while (top> && DFN[stack[top-]]>=DFN[lca])
ADD(stack[top-],stack[top]), top--;
if (lca!=stack[top]) ADD(lca,stack[top]), stack[top]=lca;
stack[++top]=x;
} void Build()
{
NUM_EDGE=; stack[top=]=;
for (int i=; i<=k; ++i)
Insert(a[i]);
while (top>=) ADD(stack[top-],stack[top]), top--;
} void DP(int x)
{
F[x]=; G[x]=;
for (int i=HEAD[x]; i; i=EDGE[i].next)
{
int y=EDGE[i].to; DP(y);
F[x]+=F[y]; G[x]+=G[y];
}
if (!vis[x]) F[x]+=(G[x]>), G[x]=(G[x]==);
else F[x]+=G[x], G[x]=;
} void Clear(int x)
{
vis[x]=false; F[x]=G[x]=;
for (int i=HEAD[x]; i; i=EDGE[i].next)
Clear(EDGE[i].to);
HEAD[x]=;
} int main()
{
scanf("%d",&n);
for (int i=; i<=n-; ++i)
{
scanf("%d%d",&u,&v);
add(u,v); add(v,u);
}
DFS(,);
scanf("%d",&m);
for (int i=; i<=m; ++i)
{
scanf("%d",&k);
for (int j=; j<=k; ++j)
scanf("%d",&a[j]), vis[a[j]]=true;
sort(a+,a+k+,cmp); flag=;
for (int j=; j<=k; ++j)
if (vis[a[j]] && vis[f[a[j]][]]) {flag=false; break;}
Build();
if (flag) DP(), printf("%d\n",F[]);
else puts("-1");
Clear();
}
}