一个思路清奇代码复杂常数大看起来很假的$DP$做法。
建出虚树,设$f(i,0)$为使点$i$的子树内的关键点互不联通,且存在关键点与点$i$联通的最小代价;$f(i,1)$为使点$i$的子树内的关键点互不联通,且不存在关键点与点$i$联通的最小代价。
若$i$为关键点:
$f(i,1)$的情况不可能成立(关键点$i$和$i$联通),$f(i,1)=inf$。
判断一下是否有$i$的儿子为关键点且与$i$在原树上有边,存在则无解。
对于$f(i,0)$,处于情况$0$的儿子为满足关键点互不联通,需断掉路径上的某个点,处于情况$1$的儿子不用管,$f(i,0)=\sum\limits_{j\in son(i)}\min\{f(j,1),f(j,0)+1\}$
若$i$不为关键点:
若$i$有不少于$2$个点为关键点,不可能存在情况$0$,此时$f(i,0)=inf$。
否则其儿子里需有且只有处于情况$0$,即$f(i,0)=\sum\limits_{j\in son(i)}f(j,1)+\min\limits_{j\in son(i)}\{f(j,0)-f(j,1)\}$
对于$f(i,1)$,要么断开点$i$,儿子随便选;要么儿子都处于情况$1$。即$f(i,1)=\min\{\left(\sum\limits_{j\in son(i)}\min\{f(j,0),f(j,1)\}\right)+1,\sum\limits_{j\in son(i)}f(j,1)\}$
最后答案为$\min\{f(1,0),f(1,1)\}$。
代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#define maxn 100005
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
int x=0,y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
namespace origin{
int seg[maxn],top[maxn],son[maxn],fa[maxn],deep[maxn],siz[maxn],h[maxn],all,num;
struct edge{
int pre,to;
}e[maxn<<1];
inline void add(int from,int to){
e[++num].pre=h[from],h[from]=num,e[num].to=to;
}
void dfs1(int node=1){
siz[node]=1;
int x;
for(register int i=h[node];i;i=e[i].pre){
x=e[i].to;
if(!siz[x]){
fa[x]=node,deep[x]=deep[node]+1,dfs1(x),siz[node]+=siz[x];
if(siz[x]>siz[son[node]])son[node]=x;
}
}
}
void dfs2(int node=1){
seg[node]=++all;
if(son[node]){
top[son[node]]=top[node],dfs2(son[node]);
int x;
for(register int i=h[node];i;i=e[i].pre){
x=e[i].to;
if(!seg[x])top[x]=x,dfs2(x);
}
}
}
int lca(int x,int y){
while(top[x]!=top[y])deep[top[x]]<deep[top[y]]?y=fa[top[y]]:x=fa[top[x]];
return deep[x]<deep[y]?x:y;
}
}
namespace virt{
int h[maxn],f[maxn][2],num,n;
bool vis[maxn],flag;
vector<int>p;
struct edge{
int pre,to;
bool l;
}e[maxn<<1];
inline void add(int from,int to){
bool l=(origin::fa[from]==to)||(origin::fa[to]==from);
e[++num].pre=h[from],h[from]=num,e[num].to=to,e[num].l=l;
e[++num].pre=h[to],h[to]=num,e[num].to=from,e[num].l=l;
}
inline bool cmp(int x,int y){return origin::seg[x]<origin::seg[y];}
struct Monostack{
int sta[maxn],top;
void push(int x){sta[++top]=x;}
void clear(){
for(register int i=2;i<=top;++i)add(sta[i],sta[i-1]);
top=0;
}
void check(int x){
if(x==1)return;
int l=origin::lca(x,sta[top]);
h[x]=0;
if(l!=sta[top]){
while(origin::seg[l]<origin::seg[sta[top-1]])add(sta[top],sta[top-1]),--top;
--top;
if(l!=sta[top])h[l]=0,add(sta[top+1],l),push(l);
else add(sta[top+1],l);
}
push(x);
}
}s;
void dfs(int node=1,int fa=0){
f[node][0]=(vis[node]^1)*n,f[node][1]=vis[node]*n;
int x,siz=0,rec=0,ma=0;
for(register int i=h[node];i;i=e[i].pre){
x=e[i].to;
if(x==fa)continue;
siz+=vis[x],dfs(x,node);
if(vis[node]){
if(vis[x]&&e[i].l)flag=1;
f[node][0]+=min(f[x][1],f[x][0]+1);
}
else {
ma=max(ma,f[x][1]-f[x][0]);
rec+=min(f[x][0],f[x][1]);
f[node][1]+=f[x][1];
}
}
if(!vis[node]){
if(siz<=1)f[node][0]=f[node][1]-ma;
f[node][1]=min(f[node][1],rec+1);
}
}
void build(){
h[1]=0,s.push(1);
for(vector<int>::iterator iter=p.begin();iter!=p.end();++iter)s.check(*iter);
s.clear();
}
void solve(){
p.clear(),flag=0,n=read(),num=0;
int x;
for(register int i=1;i<=n;++i)p.push_back(x=read()),vis[x]=1;
sort(p.begin(),p.end(),cmp);
build(),dfs();
printf("%d\n",flag?-1:min(f[1][0],f[1][1]));
for(vector<int>::iterator iter=p.begin();iter!=p.end();++iter)vis[*iter]=0;
}
}
int main(){
using namespace origin;
int n=read(),x,y;
for(register int i=1;i<n;++i)x=read(),y=read(),add(x,y),add(y,x);
dfs1(),dfs2(),n=read();
while(n--)virt::solve();
}