题目大意
小w心里的火焰就要被熄灭了。
简便起见，假设小 w 的内心是一棵 n - 1 条边，n 个节点的树。
现在你要在每个节点里放一些个灭火器，每个节点可以放任意多个。
接下来每个节点都要被分配给一个至多 k 条边远的灭火器，每个灭火器最多能分配给 s 个节点。
至少要多少个灭火器才能让小 w 彻底死心呢？
题目分析
此题是一道贪心的题目。
我们考虑对于在$u$及其子树中进行贪心。
贪心的策略如下：
先递归其子树，使得子树中的策略最优。
然后处理在当前放灭火器的情况。
显然，比$u$深$k$的结点是必须要进行匹配的。
若比$u$结点深$k$的个数为$tot$。
那么很显然我们要在$u$结点放置的灭火器数量即为$\lceil\frac{tot}{s}\rceil$。
但是这必定会多出，$\lceil\frac{tot}{s}\rceil\times s-tot$个结点，那么我们可以用这$s-tot$个结点来满足其他结点的要求。
不妨设置$f[i,j]$表示在$i$为根的子树最多经过$j$条边的所有点中还能匹配的个数，$g[i,j]$表示在$i$为根的子树最多经过$j$条边的所有点中未被匹配的个数。
显然$g[i,j]=1$，$f[i,0]=\lceil\frac{tot}{s}\rceil\times s$。
在满足了必须选取的结点后，还多出来的结点可以随便匹配，事实上我们根据贪心的思路选择将长度更长的链优先匹配。
编程实现是：枚举从根分开两条链的长度$i,j\,\,\,i+j\le k$，使得$f[u,i]$与$g[u,j]$进行匹配。
然后我们就可以写出下面的第一份代码了。
这样写是可以过的，然而还有一种优化的方法。
因为$f[],g[]$关于子树的信息是非常模糊的，我们可以勉强将$lca$处的信息向上传递，再更高层处理。
因为这部分的信息并没有丢失，而传递到了上面一定会被处理，所以我们只需要每次枚举长度为$k$与$k-1$即可，当然这样做还需要在根结点处理一下长度$\lt k-1$的信息，因为他们不能再向上传递了。
时间复杂度$O(nk)$。
代码
未优化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
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;
}
typedef long long LL;
const int maxn=100005;
vector<int>edges[maxn];
void AddEdge(int x,int y) {
edges[x].push_back(y);
}
int n,s,k,f[maxn][25],g[maxn][25],ans=0;
void Dfs(int Now,int father) {
for(auto& Next:edges[Now]) {
if(Next==father)continue;
Dfs(Next,Now);
for(int j=1; j<=k; j++) {
f[Now][j]=min(n,f[Now][j]+f[Next][j-1]);
g[Now][j]+=g[Next][j-1];
}
}
g[Now][0]++;
if(g[Now][k]) {
int tmp=ceil((double)g[Now][k]/s);
f[Now][0]=min((LL)n,(LL)tmp*s);
ans+=tmp;
}
for(int t=0; t<=k; t++)
for(int i=0; i<=k-t; i++) {
int j=k-t-i;
int tmp=min(f[Now][i],g[Now][j]);
f[Now][i]-=tmp;
g[Now][j]-=tmp;
}
}
int main() {
n=Get_Int();
s=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);
}
Dfs(1,0);
int tot=0;
for(int i=0; i<=k; i++)tot+=g[1][i];
ans+=ceil((double)tot/s);
printf("%d\n",ans);
return 0;
}
优化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
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;
}
typedef long long LL;
const int maxn=100005;
vector<int>edges[maxn];
void AddEdge(int x,int y) {
edges[x].push_back(y);
}
int n,s,k,f[maxn][25],g[maxn][25],ans=0;
void Dfs(int Now,int father) {
for(auto& Next:edges[Now]) {
if(Next==father)continue;
Dfs(Next,Now);
for(int j=1; j<=k; j++) {
f[Now][j]=min(n,f[Now][j]+f[Next][j-1]);
g[Now][j]+=g[Next][j-1];
}
}
g[Now][0]++;
if(g[Now][k]) {
int tmp=ceil((double)g[Now][k]/s);
f[Now][0]=min((LL)n,(LL)tmp*s);
ans+=tmp;
}
for(int i=0; i<=k; i++) {
int j=k-i;
int tmp=min(f[Now][i],g[Now][j]);
f[Now][i]-=tmp;
g[Now][j]-=tmp;
}
for(int i=0; i<k; i++) {
int j=k-1-i;
int tmp=min(f[Now][i],g[Now][j]);
f[Now][i]-=tmp;
g[Now][j]-=tmp;
}
}
int main() {
n=Get_Int();
s=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);
}
Dfs(1,0);
for(int i=0; i<=k; i++)
for(int j=k-i; j>=0; j--) {
int tmp=min(f[1][i],g[1][j]);
f[1][i]-=tmp;
g[1][j]-=tmp;
}
int tot=0;
for(int i=0; i<=k; i++)tot+=g[1][i];
ans+=ceil((double)tot/s);
printf("%d\n",ans);
return 0;
}
