题解：P12444 [COTS 2025] 发好奖 / Hijerarhija

· · 题解

首先，为了资本做局，员工 i 的奖金一定只有三种取值：0,1,c_i。

然后可以直接当树形背包问题做，但你发现 dp 数组的合并复杂度炸了。所以这个问题肯定不能直接当树形背包做。考虑换个思路。

注意本题的唯一特殊条件：如果 i 有正整数奖金，那么 fa_i 也有正整数奖金，也就是 i 的所有祖先都得有奖金。

可以联想到（但是有点难联想到）dfs 序，因为对于节点 v 以及它的任意一个祖先 u，都满足 u 在 dfs 序上的位置严格小于 v；同时，一颗子树内的节点，在 dfs 序上也是连续的。

那么我们在 dfs 序上做这个背包问题，设 dp_{i,j} 表示 dfs 序前 i 个员工总共拿 j 元奖金，\sum p 的最大值。转移也自然分为三种：

dp_{i+siz_{dfn_i},j}=\max(dp_{i+siz_{dfn_i},j},dp_{i,j}) dp_{i+1,j+1}=\max(dp_{i+1,j+1},dp_{i,j}) dp_{i+1,j+c_{dfn_i}}=\max(dp_{i+1,j+c_{dfn_i}},dp_{i,j}+p_{dfn_i})

注意这里的第一个转移，从 i 直接转移到 i+siz_{dfn_i} 是为了不给 dfn_i 子树内员工发放奖金。

时间复杂度 \Theta(nk)。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
#define pii pair<int,int>
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define ro(i,r,l) for(int i=r;i>=l;i--)
const int N=5005;
int n,m,a[N],b[N];
vector<int>e[N];
int dfn[N],tip,siz[N];
int dp[N][N];
void dfs(int u){
    dfn[++tip]=u;
    siz[u]=1;
    for (auto v:e[u]){
        dfs(v);
        siz[u]+=siz[v];
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    fo(i,2,n){
        int fa;
        cin>>fa;
        e[fa].push_back(i);
    }
    dfs(1);
    fo(i,1,n)
        cin>>a[i];
    fo(i,1,n)
        cin>>b[i];
    memset(dp,-0x3f,sizeof dp);
    dp[1][0]=0;
    fo(i,1,n){
        int x=dfn[i];
        fo(j,0,m){
            dp[i+siz[x]][j]=max(dp[i+siz[x]][j],dp[i][j]);
            if (j<m)
                dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]);
            if (j+b[x]<=m)
                dp[i+1][j+b[x]]=max(dp[i+1][j+b[x]],dp[i][j]+a[x]);
        }
    }
    int rs=0;
    fo(i,0,m)
        rs=max(rs,dp[n+1][i]);
    cout<<rs<<'\n';
    return 0;
}