HDU 1561（树形dp）

#include<cstdio> #include<cstring> #include<cmath> #include<vector> #include<algorithm> #include<iostream> using namespace std; int dp[210][210]; vector<int> list[210]; int N, M; void dfs(int father) { for (decltype(list[father].size())i = 0; i <list[father].size(); i++) { int child = list[father][i]; if (list[child].size() > 0) { dfs(child); } for (int j = M; j >=2; j--) { for (int k =1; k < j; k++) { dp[father][j] = max(dp[father][j], dp[father][k] + dp[child][j - k]); } } } } int main() { while (scanf("%d%d",&N,&M), N + M) { M++; memset(dp, 0, sizeof(dp)); for (int i = 1; i <= N; i++) { int a, b; cin >> a >> b; list[a].push_back(i); for (int j = 1; j <= M; j++) { dp[i][j] = b; } } dfs(0); for (int i = 0; i <= N; i++) { list[i].clear(); } cout << dp[0][M] << endl; } return 0; }