首页 > 代码库 > codeforces 613D：Kingdom and its Cities
codeforces 613D：Kingdom and its Cities
Description
Meanwhile, the kingdom of K is getting ready for the marriage of the King‘s daughter. However, in order not to lose face in front of the relatives, the King should first finish reforms in his kingdom. As the King can not wait for his daughter‘s marriage, reforms must be finished as soon as possible.
The kingdom currently consists of n cities. Cities are connected by n - 1 bidirectional road, such that one can get from any city to any other city. As the King had to save a lot, there is only one path between any two cities.
What is the point of the reform? The key ministries of the state should be relocated to distinct cities (we call such cities important). However, due to the fact that there is a high risk of an attack by barbarians it must be done carefully. The King has made several plans, each of which is described by a set of important cities, and now wonders what is the best plan.
Barbarians can capture some of the cities that are not important (the important ones will have enough protection for sure), after that the captured city becomes impassable. In particular, an interesting feature of the plan is the minimum number of cities that the barbarians need to capture in order to make all the important cities isolated, that is, from all important cities it would be impossible to reach any other important city.
Help the King to calculate this characteristic for each of his plan.
The first line of the input contains integer n (1 ≤ n ≤ 100 000) — the number of cities in the kingdom.
Each of the next n - 1 lines contains two distinct integers ui, vi (1 ≤ ui, vi ≤ n) — the indices of the cities connected by the i-th road. It is guaranteed that you can get from any city to any other one moving only along the existing roads.
The next line contains a single integer q (1 ≤ q ≤ 100 000) — the number of King‘s plans.
Each of the next q lines looks as follows: first goes number ki — the number of important cities in the King‘s plan, (1 ≤ ki ≤ n), then follow exactly ki space-separated pairwise distinct numbers from 1 to n — the numbers of important cities in this plan.
The sum of all ki‘s does‘t exceed 100 000.
For each plan print a single integer — the minimum number of cities that the barbarians need to capture, or print - 1 if all the barbarians‘ attempts to isolate important cities will not be effective.
4
1 3
2 3
4 3
4
2 1 2
3 2 3 4
3 1 2 4
4 1 2 3 4
1
-1
1
-1
7
1 2
2 3
3 4
1 5
5 6
5 7
1
4 2 4 6 7
2In the first sample, in the first and the third King‘s plan barbarians can capture the city 3, and that will be enough. In the second and the fourth plans all their attempts will not be effective.
In the second sample the cities to capture are 3 and 5.
正解：虚树+DP
解题报告：
上次考试原题...
题目要求使得k个点互相不连通的最小代价。
考虑直接构虚树，然后贪心。具体看我的代码，不再赘述。关键是虚树注意有一些细节不要写错了。
1 //It is made by jump~ 2 #include <iostream> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cstdio> 6 #include <cmath> 7 #include <algorithm> 8 #include <ctime> 9 #include <vector> 10 #include <queue> 11 #include <map> 12 #include <set> 13 using namespace std; 14 typedef long long LL; 15 #define RG register 16 const int MAXN = 100011; 17 int n,m,ecnt,id[MAXN],k; 18 int first[MAXN],next[MAXN*2],to[MAXN*2]; 19 int jump[MAXN][19],deep[MAXN]; 20 int que[MAXN],top,Stack[MAXN]; 21 int head[MAXN]; 22 int ans; 23 bool in[MAXN]; 24 struct edge{ 25 int to,next; 26 }e[MAXN]; 27 inline bool cmp(RG int a,RG int b){return id[a]<id[b];} 28 inline void link(RG int x,RG int y){ if(x==y) return ; e[++ecnt].next=head[x]; head[x]=ecnt; e[ecnt].to=y;} 29 inline int getint() 30 { 31 RG int w=0,q=0; RG char c=getchar(); 32 while((c<‘0‘ || c>‘9‘) && c!=‘-‘) c=getchar(); if (c==‘-‘) q=1, c=getchar(); 33 while (c>=‘0‘ && c<=‘9‘) w=w*10+c-‘0‘, c=getchar(); return q ? -w : w; 34 } 35 36 inline void dfs(RG int x,RG int fa){ 37 jump[x][0]=fa; id[x]=++ecnt; 38 for(int i=1;i<=18;i++) jump[x][i]=jump[jump[x][i-1]][i-1]; 39 for(int i=first[x];i;i=next[i]) { 40 RG int v=to[i]; if(v==fa) continue; 41 deep[v]=deep[x]+1; dfs(v,x); 42 } 43 } 44 45 inline int lca(RG int x,RG int y){ 46 if(deep[x]<deep[y]) swap(x,y); 47 RG int t=0; while((1<<t) <= deep[x]) t++; 48 t--; for(int i=t;i>=0;i--) if(deep[x]-(1<<i)>=deep[y]) x=jump[x][i]; 49 if(x==y) return y; 50 for(RG int i=t;i>=0;i--) if(jump[x][i]!=jump[y][i]) { x=jump[x][i]; y=jump[y][i]; } 51 return jump[x][0]; 52 } 53 54 inline int dp(RG int x,RG int fa){ 55 RG int cap=0,lin; RG bool flag=false,ff=true; 56 if(in[x]){//自己是的话，必须把所有有指挥官的儿子结点的路都堵上 57 cap++; 58 for(RG int i=head[x];i;i=e[i].next) { 59 RG int v=e[i].to; if(v==fa) continue; 60 lin=dp(v,x); cap+=lin; 61 if(lin>0) ans++; 62 } 63 } 64 else{//自己不是的话，如果只有一个儿子结点则不用管，如果超过一个则需要把当前结点摧毁，并且等价于与上面部分断开了 65 for(RG int i=head[x];i;i=e[i].next) { 66 RG int v=e[i].to; if(v==fa) continue; 67 lin=dp(v,x); cap+=lin; 68 if(lin!=0 && flag && ff) ans++,ff=false; 69 if(lin>0)flag=true;//!!!!!!只有在儿子结点有未处理的情况下才需要打标记！！！！！！ 70 } 71 if(!ff) cap=0; 72 } 73 head[x]=0; 74 return cap; 75 } 76 77 inline bool solve(){ 78 m=getint(); for(RG int i=1;i<=m;i++) que[i]=getint(),in[que[i]]=1; 79 for(RG int i=1;i<=m;i++) for(RG int j=first[que[i]];j;j=next[j]) if(in[to[j]]) return false; 80 sort(que+1,que+m+1,cmp);//按dfs序排序 81 top=0;Stack[++top]=1; RG int grand; 82 ecnt=0; 83 for(RG int i=1;i<=m;i++) { 84 grand=lca(Stack[top],que[i]); 85 while(1) { 86 if(deep[Stack[top-1]]<=deep[grand]) { 87 link(grand,Stack[top]); top--; 88 if(Stack[top]!=grand) Stack[++top]=grand; 89 break; 90 } 91 link(Stack[top-1],Stack[top]); top--; 92 } 93 if(Stack[top]!=que[i]) Stack[++top]=que[i]; 94 } 95 top--; 96 while(top) link(Stack[top],Stack[top+1]),top--; 97 ans=0; dp(1,0); 98 printf("%d\n",ans); 99 return true;100 }101 102 inline void work(){103 n=getint(); RG int x,y;104 for(RG int i=1;i<n;i++) {105 x=getint(); y=getint();106 next[++ecnt]=first[x]; first[x]=ecnt; to[ecnt]=y;107 next[++ecnt]=first[y]; first[y]=ecnt; to[ecnt]=x;108 }109 ecnt=0; deep[1]=1; dfs(1,0);110 k=getint(); for(RG int i=1;i<=k;i++) { if(!solve()) printf("-1\n"); for(int j=1;j<=m;j++) in[que[j]]=0; }111 }112 113 int main()114 {115 work();116 return 0;117 }
codeforces 613D：Kingdom and its Cities