P1051 （C++代码）

解题思路:





注意事项:





参考代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 320;
int f[maxn][maxn],bro[maxn],son[maxn],v[maxn];
void add(int fa, int s)
{
    bro[s] = son[fa];
    son[fa] = s;
}
int dp(int i, int j)
{    
if (i == -1) return 0;    
if (j == 0) return 0;    
if (f[i][j] != -1) return f[i][j];    
int m = -1<<30; //最小值 

    // 全分兄弟
    m = max( m, dp(bro[i] , j));    
    for (int k = 0; k <= j-1; k++)
    {
        m = max( m , dp(son[i] , k) + dp(bro[i] , j-1-k) + v[i]);
    }
    f[i][j] = m;    
    return m;
}
    int main()
    {    
        memset(son , -1, sizeof(son));    
        memset(bro , -1, sizeof(bro));    
        memset(f   , -1, sizeof(f  ));    
        int n, m;    
        cin>>n>>m;    
        for(int i=1;i<=n;i++)
        {        
        int fa,vx;        
        cin>>fa>>vx;
        add(fa,i);
        v[i] = vx;
    }    
        cout<<dp(0, m+1);    
        return 0;
}