前言

清楚姐姐树形题单的最后一题了...

思路

考虑先当前节点必须把当前节点前面连接到根的节点全部选了..
那么我们不妨令为选了节点且选取数量为的一个最大价值.
那么转移似乎挺简单的.

代码

#include <bits/stdc++.h>
using namespace std;
const int N=3e2+5;
vector<int>g[N];
int f[N][N],n,m,val[N];
void dfs(int u)
{
    f[u][1]=val[u];
    for(int v:g[u])
    {
        dfs(v);
        for(int j=m+1;j>=1;j--)
            for(int k=m+1;k>=1;k--)
                if(j+k<=m+1) f[u][j+k]=max(f[u][j+k],f[u][j]+f[v][k]);
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        int u;
        scanf("%d%d",&u,&val[i]);
        g[u].push_back(i);
    }
    dfs(0);
    printf("%d\n",f[0][m+1]);
    return 0;
}