Instantly share code, notes, and snippets.

Embed
What would you like to do?
BZOJ 1117: [POI2009]救火站Gas
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int kN = 1e5+10;
const int kK = 20+2;
int N, S, K;
vector<int> G[kN];
long long need[kN][kK], have[kN][kK];
int deep[kN], fa[kN];
int ans = 0;
void DFS(int u, int fa_) {
deep[u] = deep[fa_]+1;
fa[u] = fa_;
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if (v == fa_) continue;
DFS(v, u);
for (int j = 0; j < K; j++) need[u][j+1] += need[v][j];
for (int j = 1; j <= K; j++) have[u][j-1] += have[v][j];
}
need[u][0]++;
long long t = need[u][K]-have[u][K];
if (t > 0) {
int cnt = t/S;
if (t%S) cnt++;
have[u][K] += cnt*S;
ans += cnt;
}
for (int j = 0; j <= K; j++) {
for (int k = j; k >= 0 && k >= j-1; k--) {
int d = min(need[u][k], have[u][j]);
need[u][k] -= d;
have[u][j] -= d;
}
}
}
int main() {
//freopen("in.txt", "r", stdin);
scanf("%d %d %d", &N, &S, &K);
for (int i = 1; i <= N-1; i++) {
int u, v; scanf("%d %d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
DFS(1, 0);
for (int i = 0; i <= K; i++) {
for (int j = 0; j <= i; j++) {
int d = min(have[1][i], need[1][j]);
have[1][i] -= d;
need[1][j] -= d;
}
}
int t = 0;
for (int i = 0; i <= K; i++) t += need[1][i];
ans += t/S;
if (t%S) ans++;
printf("%d\n", ans);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment