HDU 1561 树形DP(入门)

时间：2022-04-15 15:29:25

题目链接:  HDU 1561 The more, The Better

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstdlib>

#include <string>

#include <cstring>

#include <algorithm>

#include <iomanip>

#include <vector>

using namespace std;

const int inf = 0x7FFFFFFF;

const int maxn = 1000000;

vector<int>V[205];

int n,m;

int dp[205][205];

bool vis[205];

void Init(){

    for(int i=0;i<=n;++i)

        V[i].clear();

    memset(dp,0,sizeof(dp));

    memset(vis,false,sizeof(vis));

    for(int i=0; i<=n; ++i)

        for(int j=2; j<=m; ++j)

            dp[i][j]=-1;

}

void DFS(int cnt){

    vis[cnt]=true;

    int len=V[cnt].size();

    for(int i=0;i<len;++i){

        int next=V[cnt][i];

        if(!vis[next]) DFS(next);

        for(int j=m;j>=2;--j)

            for(int k=1;k<j;++k)

                if(dp[next][j-k]!=-1&&dp[cnt][k]!=-1)

                    dp[cnt][j]=max(dp[cnt][j],dp[next][j-k]+dp[cnt][k]);

    }

}

int main(){

    while(~scanf("%d%d",&n,&m),n+m){

        Init();

        for(int i=1;i<=n;++i){

            int a,b;

            scanf("%d%d",&a,&b);

            dp[i][1]=b;

            V[a].push_back(i);  /// a的子结点

        }

        ++m;

        DFS(0);

        printf("%d\n",dp[0][m]);

    }

    return 0;

}

相关文章