CF613D:Kingdom and its Cities(树形DP,虚树)

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

Sample Output1

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

Sample Output2

Solution

$LCA$写错身败名裂了啊QAQ……

先建个虚树，然后特判掉无解，也就是有两个关键点相邻的情况。

判完无解后$DP$，设$F[i]$表示解决$i$子树的最小花费，$G[i]$表示$i$子树中还没有被阻断的点数。

具体转移看代码吧，也挺好懂的……

Code

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 #include<vector>
  5 #include<algorithm>
  6 #define N (100009)
  7 using namespace std;
  8 
  9 struct Edge{int to,next;}edge[N<<1];
 10 int n,u,v,m,k,dfs_num,flag;
 11 int a[N],DFN[N],Depth[N],f[N][18],vis[N],F[N],G[N];
 12 int head[N],num_edge;
 13 
 14 void add(int u,int v)
 15 {
 16     edge[++num_edge].to=v;
 17     edge[num_edge].next=head[u];
 18     head[u]=num_edge;
 19 }
 20 
 21 void DFS(int x,int fa)
 22 {
 23     f[x][0]=fa;
 24     for (int i=1; i<=17; ++i)
 25         f[x][i]=f[f[x][i-1]][i-1];
 26     DFN[x]=++dfs_num; Depth[x]=Depth[fa]+1;
 27     for (int i=head[x]; i; i=edge[i].next)
 28         if (edge[i].to!=fa) DFS(edge[i].to,x);
 29 }
 30 
 31 int LCA(int x,int y)
 32 {
 33     if (Depth[x]<Depth[y]) swap(x,y);
 34     for (int i=17; i>=0; --i)
 35         if (Depth[f[x][i]]>=Depth[y]) x=f[x][i];
 36     if (x==y) return x;
 37     for (int i=17; i>=0; --i)
 38         if (f[x][i]!=f[y][i]) x=f[x][i], y=f[y][i];
 39     return f[x][0];
 40 }
 41 
 42 struct E{int to,next;}EDGE[N<<1];
 43 int HEAD[N],NUM_EDGE;
 44 int stack[N],top;
 45 bool cmp(int u,int v) {return DFN[u]<DFN[v];}
 46 
 47 void ADD(int u,int v)
 48 {
 49     if (u==v) return;
 50     EDGE[++NUM_EDGE].to=v;
 51     EDGE[NUM_EDGE].next=HEAD[u];
 52     HEAD[u]=NUM_EDGE;
 53 }
 54 
 55 void Insert(int x)
 56 {
 57     if (top==1) {stack[++top]=x; return;}
 58     int lca=LCA(x,stack[top]);
 59     if (lca==stack[top]) {stack[++top]=x; return;}
 60     while (top>1 && DFN[stack[top-1]]>=DFN[lca])
 61          ADD(stack[top-1],stack[top]), top--;
 62     if (lca!=stack[top]) ADD(lca,stack[top]), stack[top]=lca;
 63     stack[++top]=x;
 64 }
 65 
 66 void Build()
 67 {
 68     NUM_EDGE=0; stack[top=1]=1;
 69     for (int i=1; i<=k; ++i)
 70         Insert(a[i]);
 71     while (top>=2) ADD(stack[top-1],stack[top]), top--;
 72 }
 73 
 74 void DP(int x)
 75 {
 76     F[x]=0; G[x]=0;
 77     for (int i=HEAD[x]; i; i=EDGE[i].next)
 78     {
 79         int y=EDGE[i].to; DP(y);
 80         F[x]+=F[y]; G[x]+=G[y];
 81     }
 82     if (!vis[x]) F[x]+=(G[x]>1), G[x]=(G[x]==1);
 83     else F[x]+=G[x], G[x]=1;
 84 }
 85 
 86 void Clear(int x)
 87 {
 88     vis[x]=false; F[x]=G[x]=0;
 89     for (int i=HEAD[x]; i; i=EDGE[i].next)
 90         Clear(EDGE[i].to);
 91     HEAD[x]=0;
 92 }
 93 
 94 int main()
 95 {
 96     scanf("%d",&n);
 97     for (int i=1; i<=n-1; ++i)
 98     {
 99         scanf("%d%d",&u,&v);
100         add(u,v); add(v,u);
101     }
102     DFS(1,0);
103     scanf("%d",&m);
104     for (int i=1; i<=m; ++i)
105     {
106         scanf("%d",&k);
107         for (int j=1; j<=k; ++j)
108             scanf("%d",&a[j]), vis[a[j]]=true;
109         sort(a+1,a+k+1,cmp); flag=1;
110         for (int j=1; j<=k; ++j)
111             if (vis[a[j]] && vis[f[a[j]][0]]) {flag=false; break;}
112         Build();
113         if (flag) DP(1), printf("%d
",F[1]);
114         else puts("-1");
115         Clear(1);
116     }
117 }