hdu 1561 The more, The Better(트리 dp)

제목:
나무 한 그루를 주면 나무의 뿌리가 0이고 각 노드를 점령하면 하나의 가치를 얻을 수 있지만 어떤 하위 노드의 가치를 얻으려면 반드시 이 하위 노드의 직접적인 선구자인 아버지 노드를 점령해야 한다.얻은 최대 가치가 얼마냐고 물었다.
제목은 최대 m점을 점령할 수 있도록 제시합니다.
문제풀이: 나무 가방(01) 설정 상태 dp[i][j]는 i를 뿌리 j개 노드로 얻을 수 있는 최대 가치를 나타낸다(여기 j는 뿌리 노드가 없거나 뿌리 노드가 있음을 나타낼 수 있다)
이동할 때 상태는 다음과 같아야 한다. dp[u][i]=max {dp[u][i], dp[v][i-j]+dp[v][j]} 이곳의 dp[u][i]는 뿌리 노드가 u인 i개 노드의 최대 가치를 나타낸다. 그러나 주의해라. 이곳의 i는 u라는 뿌리 노드를 포함하지 않지만 dp[v][j]의 j는 v라는 노드를 포함한다.이렇게 옮기는 것은 제목을 충족시키기 위해 아버지 노드를 먼저 점령해야 아들 노드를 점령할 수 있다며 코드를 잘 보고 이 방법의 장점을 자세히 이해하기 위해서다.검색 함수의 끝에 dp[u][i]에 대한 업데이트를 추가해야 합니다. 여기서 i는 u라는 노드를 포함하는지 여부를 표시하고 업데이트를 거꾸로 해서 후효성을 방지해야 합니다.
PS: 사실 이 문제도 상태 dp[i][j][2]0을 이렇게 정의할 수 있다. 이것은 루트 노드 i를 포함하지 않고 1은 포함을 의미한다.이렇게 하는 것은 메모리를 좀 낭비하는 것일 뿐이지 별 차이가 없다.

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<math.h>
using namespace std;
#define oo 0x3f3f3f3f
#define maxn 205
int dp[maxn][maxn];
struct Node
{
    int v,next;
}E[maxn<<1];
int head[maxn],tol;
int val[maxn];
int n,m;

void inst()
{
    memset(head,-1,sizeof head);
    tol=0;
    memset(dp,0,sizeof dp);
}

void add_edge(int u,int v)
{
    E[tol].v=v;
    E[tol].next=head[u];
    head[u]=tol++;
}

void tree_dp(int u)
{
    for(int i=head[u];i!=-1;i=E[i].next)
    {
        int v=E[i].v;
        tree_dp(v);
        for(int j=m;j>=0;j--)
            for(int k=0;k<=j;k++)
                dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]);
    }
    for(int i=m+1;i>=1;i--)
        dp[u][i]=dp[u][i-1]+val[u];
}

int main()
{
    int u,v;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        if(n==0&&m==0) break;
        inst();
        val[0]=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d %d",&v,&val[i]);
            add_edge(v,i);
        }
        tree_dp(0);
        printf("%d
",dp[0][m+1]);
    }
    return 0;
}

/*
*/