CF613D 题解

一、题目描述：

　　给你一颗 $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++!$