Codeforces Round #419C: Karen and Supermarket

http://codeforces.com/contest/815/problem/C

3乗っぽいけど2乗な木dp。
5000*5000*2のlong longの配列持ったらMLEした。
さらに初期化を適当にやりすぎてO(N^3)になってしまった。
直してAC。

int N, B;
vector<int> G[MAX_N];
int dp[MAX_N][MAX_N][2];
int dp2[MAX_N][MAX_N][2];

int C[MAX_N], D[MAX_N];
int E[MAX_N];

int loop1(int at) {
	int res = 1;
	int S = (int)G[at].size();
	rep(i, 0, S) {
		int n = G[at][i];
		res += loop1(n);
	}
	return E[at] = res;
}

void loop2(int at) {

	int S = (int)G[at].size();
	rep(i, 0, S) {
		loop2(G[at][i]);
	}
	
	int M = 0;
	rep(j, 0, E[at] + 1) {
		dp2[0][j][0] = inf;
		dp2[0][j][1] = inf;
	}
	dp2[0][0][0] = 0;
	dp2[0][0][1] = 0;

	rep(i, 0, S) {
		int n = G[at][i];
		rep(j, 0, M + E[n] + 2) {
			dp2[i + 1][j][0] = inf;
			dp2[i + 1][j][1] = inf;
		}
		rep(j, 0, M + 1) {
			rep(k, 0, E[n] + 1) {
				MIN(dp2[i + 1][j + k][0], dp[n][k][0] + dp2[i][j][0]);
				MIN(dp2[i + 1][j + k][1], dp[n][k][1] + dp2[i][j][1]);
				MIN(dp2[i + 1][j + k][0], inf);
				MIN(dp2[i + 1][j + k][1], inf);
			}
		}
		M += E[n];
	}
	dp[at][0][0] = 0;
	dp[at][0][1] = 0;
	rep(j, 1, E[at] + 1) {
		dp[at][j][0] = min(dp2[S][j - 1][0] + C[at], dp2[S][j][0]);
		dp[at][j][1] = min(dp2[S][j - 1][1] + D[at], dp2[S][j][0]);
		MIN(dp[at][j][0], inf);
		MIN(dp[at][j][1], inf);
	}
}

void solve() {
	cin >> N >> B;
	rep(i, 0, N) {
		cin >> C[i] >> D[i];
		D[i] = C[i] - D[i];
		if(i) {
			int a; cin >> a; a--;
			G[a].push_back(i);
		}
	}
	loop1(0);
	loop2(0);

	rep(i, 0, N + 1) {
		if(dp[0][i][1] > B) {
			cout << i - 1 << "\n";
			return;
		}
	}

	cout << N << "\n";
}