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"; }