404 没有上司的舞会2

// 404 没有上司的舞会2.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

/*
http://oj.daimayuan.top/course/5/problem/219

一家公司里有 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。


2 1
1
1 2

2 1
1
3 2

2 2
1
1 2

2 2
1
3 2


3 2
1 1
1 2 3

3 1
1 1
1 2 3

3 2
1 2
1 2 3

3 1
1 2
1 2 3

*/


#include <iostream>
#include <memory.h>
#include <unordered_set>

using namespace std;

const int N = 510;
int dp[N][N][2];
int h[N], e[N], ne[N], idx;
int n, m;
int val[N];
int ans;

void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u) {
	dp[u][1][1] = val[u];
	for (int i = h[u]; i != -1; i = ne[i]) {
		int j = e[i];
		dfs(j);
		for (int k = m; k >=0 ; k--) {
			for (int h = 0; h <= k; h++) {
				dp[u][k][0] = max(dp[u][k][0], dp[u][k - h][0] + dp[j][h][0]);
				dp[u][k][0] = max(dp[u][k][0], dp[u][k - h][0] + dp[j][h][1]);
				dp[u][k][1] = max(dp[u][k][1], dp[u][k - h][1] + dp[j][h][0]);
			}

			if (u == 1) {
				ans = max(ans, dp[u][k][0]);
				ans = max(ans, dp[u][k][1]);
			}
		}
	}

}

int main()
{
	memset(h, -1, sizeof h);
	cin >> n >> m;

	for (int i = 2; i <= n; i++) {
		int t; cin >> t;
		add(t, i);
	}
	for (int i = 1; i <= n; i++) {
		cin >> val[i];
	}

	dfs(1);

	cout << ans << endl;
	return 0;
}