一家公司里有 n
个员工，他们的编号分别是 1
到 n
，其中 1
号员工是公司 CEO，CEO 在公司里没有上司。除了 CEO 外，每个人都有一个直接上司。今天公司要办一个舞会，为了大家玩得尽兴，如果某个员工的直接上司来了，他/她就不想来了。i
号员工来参加舞会会为大家带来 ai
点快乐值。由于场地有大小限制，场地最多只能容纳 m
个人。现在我们想要确定一组员工参加舞会的方案，使得快乐值总和最大。请求出快乐值总和最大是多少。
输入格式
第一行两个整数 n,m
。
接下来一行 n−1
个整数 f2,f3,…,fn
，其中 fi
(1≤fi<i)
表示 i
号员工的上司的编号。
接下来一行 n
个整数 a1,a2,…,an
表示每个员工参加舞会带来的快乐值。
输出格式
一行一个整数表示答案。
样例输入
5 2
1 2 3 1
1 8 10 8 2
样例输出
16
数据规模
对于所有数据，保证 2≤n≤500,0≤m≤n,1≤ai≤100000
。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=510;
ll f[N][N][2],a[N];//f[i][j][0]表示第i个人及
int n,m;
vector<int> v[N];
void dfs(int x)
{
for(auto p:v[x])
{
dfs(p);
for(int j=m;j;--j)
for(int k=0;k<=j;++k)
{
f[x][j][1]=max(f[x][j][1],f[x][j-k][1]+f[p][k][0]);
f[x][j][0]
=max(f[x][j][0],f[x][j-k][0]+max(f[p][k][1],f[p][k][0]));
}
}
for(int j=m;j;--j) f[x][j][1]=f[x][j-1][1]+a[x];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for(int i=2;i<=n;++i)
{
int p;cin>>p;
v[p].push_back(i);
}
for(int i=1;i<=n;++i) cin>>a[i];
dfs(1);
cout<<max(f[1][m][0],f[1][m][1])<<'\n';
return 0;
}