BZOJ 1117: [POI2009]救火站Gas

bzoj_1117.cpp

#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;
}