题面

⼩ w ⼼⾥的⽕焰就要被熄灭了。简便起⻅，假设⼩ w 的内⼼是⼀棵 n − 1 条边，n 个节点的树。现在你要在每个节点⾥放⼀些个灭⽕器，每个节点可以放任意多个。接下来每个节点都要被分配给⼀个⾄多 k 条边远的灭⽕器，每个灭⽕器最多能分配给 s 个节点。⾄少要多少个灭⽕器才能让⼩ w 彻底死⼼呢？

题解

树形DP，由于k≤20k\le 20k≤20，用f[i][j]f[i][j]f[i][j]存iii这个点下面距离为jjj的未匹配点有多少个，g[i][j]g[i][j]g[i][j]存iii下面能够再往上拓展jjj长度的灭火器分配数量（一个灭火器提供sss的数量）。那么根据贪心，肯定是f[i][k]f[i][k]f[i][k]必须在iii处放灭火器，然后剩下的能配就配，因为如果可以，在下面配显然更优。

时间复杂度O(nk)O(nk)O(nk)。

CODE

#include <bits/stdc++.h>

using namespace std;

inline void rd(int &x) {

    char ch; while(!isdigit(ch=getchar()));

    for(x=ch-'0';isdigit(ch=getchar());x=x*10+ch-'0');

}

const int MAXN = 100005;

const int MAXK = 25;

int n, s, k, ans;

int fir[MAXN], to[MAXN<<1], nxt[MAXN<<1], cnt;

inline void link(int u, int v) {

    to[++cnt] = v; nxt[cnt] = fir[u]; fir[u] = cnt;

    to[++cnt] = u; nxt[cnt] = fir[v]; fir[v] = cnt;

}

int f[MAXN][MAXK], g[MAXN][MAXK];

void dfs(int u, int ff) {

    for(int i = fir[u], v; i; i = nxt[i])

        if((v=to[i]) != ff) {

            dfs(v, u);

            for(int j = 0; j < k; ++j) f[u][j+1] += f[v][j];

            for(int j = 1; j <= k; ++j) g[u][j-1] += g[v][j], g[u][j-1] = min(g[u][j-1], n);

            //此处g可能加爆int 我就因为这里考试爆了10分(没能akQAQ)

        }

    ++f[u][0];

    if(f[u][k]) {

        int need = (f[u][k]+s-1) / s;

        ans += need;

        g[u][k] += min(1ll*need*s, 1ll*n) - f[u][k];

        f[u][k] = 0;

    }

    int tmp, cur = k;

    for(int i = k; i >= 0; --i) {

        while(f[u][i] && cur >= i) {

            tmp = min(f[u][i], g[u][cur]);

            f[u][i] -= tmp, g[u][cur] -= tmp;

            if(!g[u][cur]) --cur;

        }

    }

}

int main () {

    rd(n), rd(s), rd(k);

    for(int i = 1, u, v; i < n; ++i) rd(u), rd(v), link(u, v);

    dfs(1, 0);

    int sum = 0;

    for(int i = 0; i <= k; ++i) sum += f[1][i];

    printf("%d\n", ans + (sum + s-1) / s);

}

nk

CSP模拟赛 Repulsed（树形DP）

题面

题解

CODE