题解：P9634 [ICPC 2020 Nanjing R] Monster Hunter

Dynamic_Elaina · 2025-08-18 13:12:40 · 题解

思路

引入了限制几次操作，容易想到是树上背包。

每个点都有两种状态：使用魔法和不使用，因此初次设计状态时引入一维来记录是否操作以便转移（这类题若写出方程后发现状态不独立再去掉这维）。

我们定义 dp_{u,i,0/1} 表示在 u 子树内使用了 i 次魔法，根节点使用/不使用魔法的最小代价（注意这里我用 0 代表使用了魔法，即根节点不贡献代价）。

若根节点使用魔法，代价是所有子树最小代价的和。树上背包我们做的实际上是子树一个个合并，我们可以把根节点本身当做一个子树参与合并。

若根节点使用魔法，肯定已经使用一次了 （废话），自身代价为 0：

若根节点不使用，自身的血量肯定要贡献代价：

对于子树 v，若根节点使用魔法，儿子节点的血量不用贡献代价，反之则根据儿子节点是否使用了魔法决定：

细节

转移时复制一个副本以防新状态覆盖旧状态导致错误转移。

显然一个子树能用多少次魔法取决于其大小，转移时，若根节点使用魔法，i 必须从 1 开始循环，到 size_u 结束；若不使用则从 0 开始，到 size_u-1 结束，最后把根节点的 DP 值全部输出即可。

code

#include <bits/stdc++.h>
#define int int64_t
using namespace std;
const int MAXN=2e3+10;
int t,n;
vector<int> a[MAXN];
int hp[MAXN],dp[MAXN][2][MAXN];
int tmp[2][MAXN],siz[MAXN];
int min(int x,int y){
    return x<y?x:y;
}
void dfs(int x){
    dp[x][0][1]=0;
    dp[x][1][0]=hp[x];
    siz[x]=1;
    for(int v:a[x]){
        dfs(v);
        for(int i=0;i<=siz[x];++i){
            tmp[0][i]=dp[x][0][i];
            dp[x][0][i]=0x3f3f3f3f3f3f3f3fll;
            tmp[1][i]=dp[x][1][i];
            dp[x][1][i]=0x3f3f3f3f3f3f3f3fll;
        }
        for(int i=0;i<=siz[x];++i){
            for(int j=0;j<=siz[v];++j){
                if(i>0){
                    dp[x][0][i+j]=min(dp[x][0][i+j],tmp[0][i]+min(dp[v][0][j],dp[v][1][j]));
                }
                if(i<siz[x]){
                    dp[x][1][i+j]=min(dp[x][1][i+j],tmp[1][i]+min(dp[v][0][j],dp[v][1][j]+hp[v]));
                }
            }
        }
        siz[x]+=siz[v];
    }
}
signed main()
{
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;++i){
            a[i].clear();
            for(int j=0;j<=n;++j){
                dp[i][0][j]=dp[i][1][j]=0x3f3f3f3f3f3f3f3fll;
            }
        }
        for(int i=2;i<=n;++i){
            int p;
            cin>>p;
            a[p].emplace_back(i);
        }
        for(int i=1;i<=n;++i){
            cin>>hp[i];
        }
        dfs(1);
        for(int i=0;i<=n;++i){
            cout<<min(dp[1][0][i],dp[1][1][i])<<' ';
        }
        cout<<endl;
    }
    return 0;
}