洛谷P2014 选课

树形背包QwQ

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define maxn 310

using namespace std;

struct node
{
    int ed,nxt;
};
node edge[maxn<<1];
int n,m,first[maxn],cnt;
int num[maxn],siz[maxn],dp[maxn][maxn];

inline void add_edge(int s,int e)
{
    ++cnt;
    edge[cnt].ed=e;
    edge[cnt].nxt=first[s];
    first[s]=cnt;
    return;
}

inline void dfs(int now,int fa)
{
    siz[now]=1;
    dp[now][0]=0;
    for(register int i=first[now];i;i=edge[i].nxt)
    {
        int e=edge[i].ed;
        if(e!=fa)
        {
            dfs(e,now);
            siz[now]+=siz[e];
            for(register int j=m;j>=0;--j)
                for(register int k=min(j,siz[e]);k>=0;--k)
                    dp[now][j]=max(dp[now][j],dp[now][j-k]+dp[e][k]);
        }
    }
    if(now!=0)
       for(register int i=m;i>0;--i)
            dp[now][i]=dp[now][i-1]+num[now];
    return;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(register int i=1;i<=n;++i)
    {
        int e;
        scanf("%d%d",&e,&num[i]);
        add_edge(i,e);
        add_edge(e,i);
    }
    dfs(0,-1);
    printf("%d
",dp[0][m]);
    return 0;
}