一、题目描述：
给你一颗 $n$ 个点的树，有 $m$ 组询问。
一个点如果被攻占，那么这个点就不能通行了。
第 $i$ 次询问给出 $k_i$ 个关键点，关键点不能被攻占。
求最少攻占多少个点可以使得关键点两两不连通。若不可能，输出 $-1$。
数据范围：$1\le n,m\le 1\times 10^5,1\le k_i\le n,\sum_{i=1}^mk_i\le 1\times 10^5$。
二、解题思路：
虚树板子题。话说虚树也太明显了吧？
唯一需要注意的是当有两个儿子都是关键时不能直接返回，因为可能还有儿子没有统计答案。
时间复杂度 $O(nlog_2^n)$。瓶颈在于计算 $lca$。
三、完整代码：
1 #include<bits/stdc++.h> 2 #define V e[i].v 3 #define N 100010 4 #define rep(i,l,r) for(int i=l;i<=r;i++) 5 #define per(i,r,l) for(int i=r;i>=l;i--) 6 using namespace std; 7 int n,m,tot,ans,flag; 8 int f[N],g[N],q[N],r,stk[N],top; 9 int a[N],fa[N][20],du[N],dfn[N]; 10 struct EDGE{ 11 int v,nxt; 12 }e[N<<3]; 13 int head[N],head2[N],cnt; 14 void add(int u,int v){ 15 e[++cnt].v=v; 16 e[cnt].nxt=head[u]; 17 head[u]=cnt; 18 } 19 void add2(int u,int v){ 20 e[++cnt].v=v; 21 e[cnt].nxt=head2[u]; 22 head2[u]=cnt; 23 } 24 bool cmp(int d1,int d2){return dfn[d1]<dfn[d2];} 25 void dfs1(int u,int ff){ 26 du[u]=du[ff]+1; dfn[u]=++tot; fa[u][0]=ff; 27 for(int i=head[u];i!=-1;i=e[i].nxt) if(V!=ff) dfs1(V,u); 28 } 29 int Lca(int u,int v){ 30 if(du[u]<du[v]) swap(u,v); 31 per(i,19,0) if(du[u]-(1<<i)>=du[v]) u=fa[u][i]; 32 if(u==v) return u; 33 per(i,19,0) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i]; 34 return fa[u][0]; 35 } 36 void dfs2(int u){ 37 g[u]=f[u]; for(int i=head2[u];i!=-1;i=e[i].nxt){ 38 dfs2(V); if(g[V]) g[u]++; 39 if(f[u]&&f[V]&&fa[V][0]==u) flag=1; 40 } if(f[u]) ans+=g[u]-1; else if(g[u]>1) ans++,g[u]=0; 41 } 42 void solve(){ 43 int cc; cin>>cc; rep(i,1,cc) cin>>a[i],f[a[i]]=1; 44 sort(a+1,a+1+cc,cmp); stk[top=1]=1; r=ans=flag=0; 45 rep(i,1,cc){ 46 if(a[i]==1) continue; 47 int lca=Lca(stk[top],a[i]); q[++r]=lca; 48 if(lca!=stk[top]){ 49 while(dfn[lca]<dfn[stk[top-1]]) 50 add2(stk[top-1],stk[top]),top--; 51 add2(lca,stk[top]); 52 if(dfn[lca]>dfn[stk[top-1]]) 53 stk[top]=lca; else top--; 54 } stk[++top]=a[i]; 55 } 56 rep(i,1,top-1) add2(stk[i],stk[i+1]); 57 dfs2(1); cout<<(flag?-1:ans)<<'\n'; 58 rep(i,1,r) head2[q[i]]=-1; 59 rep(i,1,cc) head2[a[i]]=-1,f[a[i]]=0; 60 } 61 int main(){ 62 ios::sync_with_stdio(false); 63 cin.tie(0);cout.tie(0); 64 cin>>n; rep(i,1,n) head[i]=head2[i]=-1; 65 rep(i,1,n-1){ 66 int u,v; cin>>u>>v; 67 add(u,v); add(v,u); 68 } 69 dfs1(1,0); rep(i,1,19) rep(j,1,n) 70 fa[j][i]=fa[fa[j][i-1]][i-1]; 71 cin>>m; rep(i,1,m) solve(); 72 return 0; 73 }
四、写题心得：
这几天一边考试一边发现了好多遗漏的知识点，虚树是其中之一：
$1、其实虚树真的很板，只需要建树和暴力\ dp\ 就行了。=> Exp++!$
$2、dfs\ 的时候不要\ dp\ 到一半就贸然返回，可能还有没统计到的儿子节点。=> Exp++!$