/* http://acm.hdu.edu.cn/showproblem.PHP?pid=1561 The more,The Better 依赖背包 -> 树形dp 题意: 给一个树形结构,问最多拿max个城市 ,能获得的最大价值多少,拿下面的一定要先拿上面的。 解题思路: 定义状态dp[i][j] : 当前i节点及其子树下最多选择j个城市的最大值为dp[i][j]; 我们考虑到特殊状态:i节点下没有孩子那么dp[i][2,3,4,5...]均为-1(因为多选总比少选好,并且选择完后城市总是有剩余) 1. 判断当前节点P有没有孩子,如果有则令当前节点为P重复(1)操作,如果没有则到(2)操作; 2. 将当前节点P的状态更新到期父节点上, 更新操作为dp[P'father][i] = max(dp[P'father][i],dp[P'father][j]+dp[P][k]) (j + k = i,j>0,k>0,2<=i<=max_cost,对于每一个i遍历每一种(j,k)组合) 这里的dp[P'father][j] j个城市一定是没有包括P城市的其他j个城市的最大值 直到遍历到root节点即可(dp[0][i]) 3.输出dp[0][max_cost] max_cost 为题目中所给出的最多取几个城市 7 4 2 2 0 1 0 4 2 1 7 1 7 6 2 2 [i]:v 表示 第i个节点的价值为v; [0]root没有价值相当于[0]:0 [0]root / \ [2]:1 [3]:4 / | \ [1]:2 [4]:1 [7]:2 / \ [5]:1 [6]:6 */ #include <cmath> #include <queue> #include <vector> #include <cstdio> #include <string> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define CLR(c,v) memset(c,v,sizeof(c)) template <typename _T> _T Max(_T a,_T b){ return (a>b)?(a):(b); } template <typename _T> _T Max(_T a,_T b,_T c){ return (a>Max(b,c))?(a):(Max(b,c)); } template <typename _T> _T Min(_T a,_T b){ return (a<b)?(a):(b); } template <typename _T> _T Min(_T a,_T c){ return (a<Min(b,c))?(a):(Min(b,c)); } const int inf = -(1<<30); const int INF = (1<<30); const int M = 2e2 + 10; vector <int > list[M]; int dp[M][M]; int n,max_cost; void dfs(int father){ for (int i = 0 ; i < list[father].size() ; i++){ int child = list[father][i]; // 子节点 if(list[child].size() > 0) dfs(child); for(int j = max_cost ; j > 1 ; j--){// 保证从父节点开始,至少取j个城市,j>1 至少包括了这个父节点 for(int k = 1 ; k < j ; k++ ){ // 遍历每一种 k + j-k == j组合 dp[father][j] = Max(dp[father][j],dp[father][k] + dp[child][j-k]); } } } } int main(){ freopen("in.txt","r",stdin); while(cin >> n >> max_cost,n&&max_cost){ max_cost ++; // 因为数据给出的是森林,我们加入一个root节点,因此相当于允许多拿一个城市。 CLR(dp,0); for(int i = 1 ; i <= n ; i ++){ int a,b; cin >> a >> b; list[a].push_back(i); for(int j = 1 ; j <= max_cost ; j++) dp[i][j] = b; // 初始化时,每个节点,所有状态都是拿自己一个 } dfs(0); for(int i = 0 ; i <= n ; i ++) list[i].clear(); cout << dp[0][max_cost] << endl; } return 0; }