自动搬运

查看原文

来自洛谷，原作者为

	崛起的滑稽 光与对立贴贴~

搬运于2025-08-24 22:50:17，当前版本为作者最后更新于2025-08-18 13:12:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

思路

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

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

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

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

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

$$dp_{u,1,0}=0$$

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

$$dp_{u,0,1}=hp_u$$

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

$$dp_{u,i+j,0}=dp_{u,i,0}+\min(dp_{v,j,0},dp_{v,j,1})\\ dp_{u,i+j,1}=dp_{u,i,1}+\min(dp_{v,j,0},dp_{v,j,1}+hp_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;
}