HDU-1561 The more,The BetterツリーDP

http://acm.hdu.edu.cn/showproblem.php?pid=1561
問題は大まかには言わないが、中国語の問題ばかり・・この問題は複雑に見えるが、授業中に考えてみると、ノードごとにT回攻撃すると、子どもに割り当てられる回数の組み合わせ数は膨大である.しかし、この問題は暴力的で、DFSの下で三重for循環しています.forサイクルの中はリュックサックの過程です.呉濤の提案はプログラムをより良くし、再帰的に攻撃できる回数を1つ減らすことで、多くの不要なif判断を減らすことができる.
コードは次のとおりです.

#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define MAXN 205
using namespace std;

struct Node
{
    int place, next;
}edge[MAXN*3];

int head[MAXN], tol, val[MAXN];
int dp[MAXN][MAXN], M, N;

inline void modify(int s1, int s2)
{
    edge[tol].place = s2;
    edge[tol].next = head[s1];
    head[s1] = tol++;
}

bool getint( int &t )
{
    char c;  int f = 1;
    while( c = getchar(), c != '-' && ( c < '0' || c > '9' ) )
    {
        if( c == EOF )
            return false;
    } 
    if( c == '-' )
        f = -1;
    else
        t = c - '0';
    while( c = getchar(), c >= '0' && c <= '9' )
        t = t * 10 + c -'0';
    t *= f;
    return true;
}


void dfs(int f, int m)
{
    int place, v;
    dp[f][1] = val[f];  //             
    for (int i = head[f]; i != -1; i = edge[i].next)
    {
        place = edge[i].place; 
        if (m > 1)
            dfs(place, m-1);
        for (int j = m; j >= 1; --j)  //            
        {
            v = j+1;
            for (int k = 1; k <= j; ++k)  //            
            {
                if (dp[f][v] < dp[f][v-k]+dp[place][k])
                {
                    dp[f][v] = dp[f][v-k] + dp[place][k];
                }
            }
        }  //        
    }
}

int main()
{
    int s, v;
    while (scanf("%d %d", &N, &M), M | N)
    {
        tol = 0; 
        val[0] = 0;
        memset(head, -1, sizeof(head));
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= N; ++i)
        {
             getint(s), getint(v);
             val[i] = v; 
             modify(s, i);
        }
        dfs(0, M+1);
        printf("%d
", dp[0][M+1]);
    }
}