…
O(nm^2)
https://vijos.org/records/543919bc17f3cade3fb0a871
//}/* .................................................................................................................................. */
const int N = int(3e2) + 9;
VI adj[N]; int f[N][N], val[N];
int n, m;
void dfs(int u = 0){
ECH(it, adj[u]){
int v = *it; dfs(v);
DWN_1(i, m, 1) REP_1(j, i) checkMax(f[u][i], f[u][i-j]+f[v][j]);
}
DWN_1(i, m, 1) f[u][i] = f[u][i-1] + val[u];
}
int main(){
#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
REP_1_C(i, RD(n, m)){
adj[RD()].PB(i);
RD(val[i]);
}
++m; dfs();
OT(f[0][m]);
}
O(nm)
https://vijos.org/records/5411eea148c5fcdb208b4568
//}/* .................................................................................................................................. */
const int N = int(3e2) + 9;
VI adj[N]; int f[N][N], val[N];
int n, m;
void dfs(int u = 0){
ECH(it, adj[u]){
int v = *it; REP(i, m) f[v][i] = f[u][i] + val[v]; // 强制在 u 的当前状态（所有 dfs 序在 v 之前的节点所形成的泛化物品）中放入物品 v。。作为 v 的初始状态。。。
dfs(v); REP_1(i, m) checkMax(f[u][i], f[v][i-1]); // 泛化物品的并。。。
}
}
int main(){
REP_1_C(i, RD(n, m)){
adj[RD()].PB(i);
RD(val[i]);
}
dfs();
OT(f[0][m]);
}
