很休闲的一个题啊
其实一看到关于(sum k)的限制，就知道是个虚树的题了
首先我们把虚树建出来，然后考虑怎么计算个数呢？
我们令(f[x])表示以(x)的子树中，剩余了多少个还没有切断的关键点
首先，如果当前点是一个关键点的话，那么他所有的(f[son]!=0)的儿子都需要割掉，而且当前点的(f[x])应该是1（因为只能删除非关键点）
如果当前点不是一个关键点的话，如果他有一个(f[x])不为0的儿子，那么(f[x]=f[son])，不然的话，就需要把这个点删掉（不能让他的儿子通过这个点联通起来），并且(f[x]=0)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define mk makr_pair
#define ll long long
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
const int maxn = 2e5+1e2;
const int maxm = 2*maxn;
int point[maxn],nxt[maxm],to[maxm];
int cnt,n,m;
int dfn[maxn],deep[maxn],f[maxn][21];
int tag[maxn];
int tot,top,s[maxn];
int ans;
int size[maxn];
int dp[maxn];
int a[maxn],k;
bool ymh;
void addedge(int x,int y)
{
nxt[++cnt]=point[x];
to[cnt]=y;
point[x]=cnt;
}
void dfs(int x,int fa,int dep)
{
deep[x]=dep;
dfn[x]=++tot;
for (int i=point[x];i;i=nxt[i])
{
int p = to[i];
if (p==fa) continue;
f[p][0]=x;
dfs(p,x,dep+1);
}
}
void init()
{
for (int j=1;j<=20;j++)
for (int i=1;i<=n;i++)
f[i][j]=f[f[i][j-1]][j-1];
}
int go_up(int x,int d)
{
for (int i=0;i<=20;i++)
if ((1 << i) & d)
x=f[x][i];
return x;
}
int lca(int x,int y)
{
if(deep[x]>deep[y]) x=go_up(x,deep[x]-deep[y]);
else y =go_up(y,deep[y]-deep[x]);
if (x==y) return x;
for (int i=20;i>=0;i--)
{
if (f[x][i]!=f[y][i])
{
x=f[x][i];
y=f[y][i];
}
}
return f[x][0];
}
bool cmp(int a,int b)
{
return dfn[a]<dfn[b];
}
void solve()
{
cnt=0;
sort(a+1,a+1+k,cmp);
top=1;
s[top]=1;
for (int i=1;i<=k;i++)
{
int l = lca(s[top],a[i]);
if (l!=s[top])
{
while (top>1)
{
if (dfn[s[top-1]]>dfn[l])
{
addedge(s[top-1],s[top]);
top--;
}
else
{
if (dfn[s[top-1]]==dfn[l])
{
addedge(s[top-1],s[top]);
top--;
break;
}
else
{
addedge(l,s[top]);
s[top]=l;
break;
}
}
}
}
if (s[top]!=a[i]) s[++top]=a[i];
}
while (top>1)
{
addedge(s[top-1],s[top]);
top--;
}
}
void dpp(int x,int flag)
{
int yy =0;
dp[x]=0;
if (tag[x]==flag)
{
dp[x]=1;
for (int &i=point[x];i;i=nxt[i])
{
int p = to[i];
dpp(p,flag);
if (tag[p]==flag && tag[x]==flag && deep[p]-deep[x]==1) ymh=0;
if (dp[p]>0) ans++;
}
}
else
{
dp[x]=0;
for(int &i=point[x];i;i=nxt[i])
{
int p = to[i];
dpp(p,flag);
if (tag[p]==flag && tag[x]==flag && deep[p]-deep[x]==1) ymh=0;
if (dp[p]>0) yy++,dp[x]+=dp[p];
}
if (yy>=2) dp[x]=0,ans++;
}
}
int main()
{
n=read();
for (int i=1;i<n;i++)
{
int x=read(),y=read();
addedge(x,y);
addedge(y,x);
}
dfs(1,0,1);
init();
memset(point,0,sizeof(point));
m=read();
for (int i=1;i<=m;i++)
{
k=read();
ans=0;
ymh=true;
for (int j=1;j<=k;j++) a[j]=read(),tag[a[j]]=i;
solve();
dpp(1,i);
// cout<<ymh<<endl;
if (!ymh) ans=-1;
cout<<ans<<"
";
}
return 0;
}