第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（南京）M Monster Hunter —

第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（南京）M Monster Hunter —— 树形DP

本文主要是介绍第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（南京）M Monster Hunter —— 树形DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

现在有一棵根为1的树，你要将所有点消除，消除一个点i首先需要消除它的父亲，然后消除i的代价是
在这里插入图片描述
也就是hp[i]+还未被消除的所有儿子的hp和
你有一种魔法可以无视所有规则消除掉一个点。
问你这个魔法的使用次数为i(0<=i<=n)次时，最少需要的代价是多少。

题解：

很明显是树形DP，但是枚举儿子的状态转移的话，时间复杂度会变成 $n^3$ ，所以需要使用上下界优化
那么消除当前数的时候，需要加上所有未被消除的儿子的值，因此DP需要三维
dp[i][j][k]表示到了第i个点，使用了j次魔法，当前点是否一开始就使用魔法消除时最小的代价。
那么边界值：
dp[x][1][0]=0
dp[x][0][1]=a[x]
然后转移：
首先是这个点在一开始就被消除
dp[x][i+j][0]=min(dp[x][i+j][0],dp[x][i][0]+min(dp[ne][j][0],dp[ne][j][1]));
还有一种就是这个点按照常规的消除方法，它需要加上儿子的代价
dp[x][i+j][1]=min(dp[x][i+j][1],dp[x][i][1]+min(dp[ne][j][0],dp[ne][j][1]+a[ne]));

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int N=2e3+5;
ll dp[N][N][2],a[N];
const ll inf=1e18;
vector<int>son[N];
int siz[N];
ll tmp[N];
void dfs(int x){siz[x]=1;dp[x][0][0]=inf,dp[x][1][0]=0;//dp[x][0][1]=a[x];int f=0;for(int ne:son[x]){dfs(ne);for(int i=0;i<=siz[x]+siz[ne];i++)tmp[i]=inf;for(int i=0;i<=siz[x];i++){if(dp[x][i][0]==inf)continue;for(int j=0;j<=siz[ne];j++)tmp[i+j]=min(tmp[i+j],dp[x][i][0]+min(dp[ne][j][0],dp[ne][j][1]));}siz[x]+=siz[ne];for(int i=0;i<=siz[x];i++)dp[x][i][0]=tmp[i];}//for(int i=1;i<=siz[x];i++)dp[x][i][1]=dp[x][i][0]+a[x];//int s=vec[x].size();ll sum=0,v=0;dp[x][0][1]=a[x];siz[x]=1;for(int ne:son[x]){for(int i=0;i<=siz[x]+siz[ne];i++)tmp[i]=inf;for(int i=0;i<=siz[x];i++){if(dp[x][i][1]>=inf)continue;for(int j=0;j<=siz[ne];j++)tmp[i+j]=min(tmp[i+j],dp[x][i][1]+min(dp[ne][j][0],dp[ne][j][1]+a[ne]));}siz[x]+=siz[ne];for(int i=0;i<=siz[x];i++)dp[x][i][1]=tmp[i];}
}
int main()
{int t;scanf("%d",&t);while(t--){int n,x;scanf("%d",&n);for(int i=1;i<=n;i++)son[i].clear(),siz[i]=0;for(int i=1;i<=n;i++)for(int j=0;j<=n;j++)for(int k=0;k<=1;k++)dp[i][j][k]=inf;for(int i=2;i<=n;i++)scanf("%d",&x),son[x].push_back(i);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);dfs(1);for(int i=0;i<=n;i++)printf("%lld%c",min(dp[1][i][0],dp[1][i][1])," \n"[i==n]);}return 0;
}