隐藏
「bzoj省队十连测Day2 A」深邃 - 二分+贪心 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「bzoj省队十连测Day2 A」深邃 - 二分+贪心

题目大意

    有一棵$n$个结点的树中有$k$个关键点,要求你将树分为几个连通块,使得每个连通块包含至少一个关键点,使得最大连通块最小。求出最大连通块最小时的大小。


题目分析

最大值最小化,使用二分。
二分答案,设每个连通块大小最大为$k$,考虑其是否有解。

我们可以采用贪心的策略判定是否有解。
每个连通块最多包含一个关键点。

首先,若当前结点是关键点,与其未包含关键点的子树合并成块。
若当前结点非关键点,从儿子中找到一个含有关键点的最小的连通块,将其与当前未包含关键点的连通块合并。
若当前结点所在子树中,未包含关键点的个数$\gt k$,无解。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=200005;

bool bj,a[maxn],Have[maxn];
int n,k,Size[maxn];
vector<int>edges[maxn];

void AddEdge(int x,int y) {
edges[x].push_back(y);
}

void TreeDp(int Now,int fa,int limit) {
if(bj==0)return;
Size[Now]=1;
Have[Now]=0;
int Min=INT_MAX/2;
for(int Next:edges[Now]) {
if(Next==fa)continue;
TreeDp(Next,Now,limit);
if(!Have[Next])Size[Now]+=Size[Next];
else Min=min(Min,Size[Next]);
}
if(Size[Now]>limit) {
bj=0;
return;
}
if(a[Now]) {
Have[Now]=1;
return;
}
if(Min+Size[Now]<=limit) {
Size[Now]+=Min;
Have[Now]=1;
}
}

bool Check(int limit) {
bj=1;
TreeDp(1,0,limit);
return Have[1]&&bj;
}

int main() {
n=Get_Int();
k=Get_Int();
for(int i=1; i<n; i++) {
int x=Get_Int(),y=Get_Int();
AddEdge(x,y);
AddEdge(y,x);
}
for(int i=1; i<=k; i++)a[Get_Int()]=1;
int Left=1,Right=n;
while(Left<=Right) {
int mid=(Left+Right)>>1;
if(Check(mid))Right=mid-1;
else Left=mid+1;
}
printf("%d\n",Left);
return 0;
}
姥爷们赏瓶冰阔落吧~