\(n\) 只有 \(2000\)，这样的话我们可以开二维的 dp 了，所以我们大胆一点，定义 \(f_{u,i}\) 表示在 \(u\) 号点，用了 \(i\) 次操作后的代价。
似乎就是一个裸的树上背包了。
考虑一下如何合并，对于 \(u\) 结点，之前的儿子节点已经处理完了，我们现在如何合并到当前的状态。
我们好像要开两个数组，一个 \(f_{u,i}\) 表示 \(u\) 这个节点不用技能的最小代价，而 \(g_{u,i}\) 表示 \(u\) 这个节点用技能的最小代价。这样的话我们就能处理在 \(u\) 节点的合并问题了。我们分别考虑如何转移。
\(f_{u,i}=a_u+\min_{j+k=i}\{\min\{f_{v,j}+a_v,g_{v,j}\}+\min\{f_{u,k},g_{u,k}\}\}\}\)
\(g_{u,i}=\min_{j+k=i-1}\{\min\{f_{v,j},g_{v,j}\}+\min\{f_{u,k},g_{u,k}\}\}\}\)
竟然也靠自己 A 了。树形 dp 还是记得一点的 /se。
#include <bits/stdc++.h>
using namespace std;
template <typename T>inline void read(T& t){t=0; register char ch=getchar(); register int fflag=1;while(!('0'<=ch&&ch<='9')) {if(ch=='-') fflag=-1;ch=getchar();}while(('0'<=ch&&ch<='9')){t=t*10+ch-'0'; ch=getchar();} t*=fflag;}
template <typename T,typename... Args> inline void read(T& t, Args&... args) {read(t);read(args...);}
const int N=2e3+10;
typedef long long ll;
const ll inf=1ll<<60;
int T,fa[N],a[N],sz[N];
ll f[N][N],g[N][N],tmp[N];
vector<int>G[N];
void dfs(int u){
sz[u]=1;
g[u][0]=inf;
for(int v:G[u]){
dfs(v);
for(int i=0;i<=sz[u]+sz[v];++i) tmp[i]=inf;
for(int i=0;i<sz[u];++i)
for(int j=0;j<=sz[v];++j)
tmp[i+j]=min(tmp[i+j],f[u][i]+min(f[v][j]+a[v],g[v][j]));
for(int i=0;i<sz[u]+sz[v];++i) f[u][i]=tmp[i];
for(int i=0;i<=sz[u]+sz[v];++i) tmp[i]=inf;
for(int i=1;i<=sz[u];++i)
for(int j=0;j<=sz[v];++j)
tmp[i+j]=min(tmp[i+j],g[u][i]+min(f[v][j],g[v][j]));
for(int i=0;i<sz[u]+sz[v];++i) g[u][i]=tmp[i];
sz[u]+=sz[v];
}
for(int i=0;i<sz[u];++i) f[u][i]+=a[u];
}
int main(){
read(T);
while(T--){
int n;
read(n);
for(int i=1;i<=n;++i) G[i].clear();
for(int i=2;i<=n;++i){
read(fa[i]);
G[fa[i]].push_back(i);
}
for(int i=1;i<=n;++i) read(a[i]);
for(int i=0;i<=n;++i) for(int j=0;j<=n;++j) f[i][j]=g[i][j]=0;
dfs(1);
for(int i=0;i<=n;++i) printf("%lld ",min(f[1][i],g[1][i]));
puts("");
}
return 0;
}
/*
是谁挥霍的时光啊，是谁苦苦的奢望啊
这不是一个问题，也不需要你的回答
No answer.
*/