题解：P16189 [COI 2018] Paprike 胡椒

· · 题解

先正常按题目设状态。

定一个 dp 数组代表，切最小刀数后，以 i 为根的子树中所有花环辣度小于等于 k。

但是，会发现无法处理题目条件。

多能吃辣度不超过 k 的花环。

所以再加入一个数组储存花环辣度。

定义 sum_i 为，切 dp_i 刀后，i 所链接的花环辣度。

那么对于 x，它是否能与它的孩子 y 相连，取决于再加上 sum_y 是否会超过 k。

使用贪心，优先选择小的 sum_y 保留。

排序后，依次累加，直到超出。

以下是代码。

#include <bits/stdc++.h>
using namespace std;
int sum[1000005];//切dp[i]刀后，i所链接的花环辣度
int dp[1000005];//切dp[i]刀后,i的树中所有花环辣度小于等于k
int w[1000005];//辣度
vector <int> a[1000005];
int n,k;
struct node{
    int d,s;
};
bool cmp(node x,node y){
    return x.s < y.s;//优先选择小的保留
}
void dfs(int x,int fa){
    for (int i = 0; i < a[x].size(); i++) {int y = a[x][i];if (y != fa) dfs(y,x);}
    vector <node> v;
    for (int i = 0; i < a[x].size(); i++) {int y = a[x][i];if (y != fa){v.push_back({dp[y],sum[y]}),dp[x]+=dp[y];}}
    sort(v.begin(),v.end(),cmp);
    int cnt = w[x];
    for (int i = 0; i < v.size(); i++){
        if (cnt + v[i].s > k){
            dp[x] += v.size()-i;//保留了0~i-1,即删去了v.size()-i
            break;
        }
        cnt += v[i].s;
    }
    sum[x] = cnt;
}
int main(){
    cin>> n >> k;
    for (int i = 1; i <= n; i++) cin >> w[i];
    for (int i = 1; i <= n-1; i++){
        int u,v;
        cin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    dfs(1,0);
    cout << dp[1];
    return 0;
}