【NOIP2017提高A组模拟10.7】Repulsed

时间:2022-12-17 13:18:41

Description:

小w 心里的火焰就要被熄灭了。
简便起见,假设小w 的内心是一棵n -1 条边,n 个节点的树。
现在你要在每个节点里放一些个灭火器,每个节点可以放任意多个。
接下来每个节点都要被分配给一个至多k 条边远的灭火器,每个灭火器最多能分配给s 个节点。
至少要多少个灭火器才能让小w 彻底死亡呢?
n <= 10^5, k <= 20, s <= 10^9

题解:

贪心题都是很好骗分的。

fi,k gi,k 分别表示到i这个点,它的子树中,到它距离为k的灭火器能提供的数量,和需求的点数。

如果某些没有确定点到i距离已经等于k,显然一定要满足,不能满足就要在i点放灭火器。

如果有灭火器的距离加上未确定点的距离等于k,k-1,显然在i这里就要匹配了,不然往上走一格,距离增加了2,就超过了k,这样是不行的。

Code:

#include<cstdio> 
#define ll long long
#define fo(i, x, y) for(int i = x; i <= y; i ++)
#define fd(i, x, y) for(int i = x; i >= y; i --)
using namespace std;

const int N = 100005;

int n, s, k, x, y, ans;
int final[N], next[N * 2], to[N * 2], tot;
ll f[N][21], g[N][21]; int bz[N];

void link(int x, int y) {
next[++ tot] = final[x], to[tot] = y, final[x] = tot;
next[++ tot] = final[y], to[tot] = x, final[y] = tot;
}

void Gao(int x) {
if(f[x][0] >= g[x][k])
f[x][0] -= g[x][k], g[x][k] = 0; else
g[x][k] -= f[x][0], f[x][0] = 0;
}

void dg(int x) {
bz[x] = 1;
{
g[x][0] = 1;
for(int i = final[x]; i; i = next[i]) {
int y = to[i]; if(bz[y]) continue;
dg(y);
fo(j, 0, k - 1) f[x][j + 1] += f[y][j], g[x][j + 1] += g[y][j];
}
while(g[x][k]) {
ans ++;
if(g[x][k] <= s)
f[x][0] = s - g[x][k], g[x][k] = 0; else
g[x][k] -= s;
}
fo(i, 0, k) {
if(f[x][i] >= g[x][k - i])
f[x][i] -= g[x][k - i], g[x][k - i] = 0; else
g[x][k - i] -= f[x][i], f[x][i] = 0;
}
fo(i, 0, k - 1) {
if(f[x][i] >= g[x][k - i - 1])
f[x][i] -= g[x][k - i - 1], g[x][k - i - 1] = 0; else
g[x][k - i - 1] -= f[x][i], f[x][i] = 0;
}
}
bz[x] = 0;
}

int main() {
freopen("repulsed.in", "r", stdin);
freopen("repulsed.out", "w", stdout);
scanf("%d %d %d", &n, &s, &k);
s = n < s ? n : s;
fo(i, 1, n - 1) {
scanf("%d %d", &x, &y);
link(x, y);
}
dg(1);
fd(i, k, 0) {
while(g[1][i]) {
fd(j, k - i, 0) {
if(f[1][j] >= g[1][i]) {
f[1][j] -= g[1][i]; g[1][i] = 0;
break;
} else {
g[1][i] -= f[1][j]; f[1][j] = 0;
}
}
if(g[1][i]) ans ++, f[1][0] += s;
}
}
printf("%d", ans);
}