POJ-1155 TELE 树形背包dp

dp[u][i]代表以u为根的子树选i个叶子的最大收益

那么dp[u][i]=max(dp[u][i],dp[v][k]+dp[u][i-k]-len) (1=<k<=i)

细节看代码：

#include<iostream>

#include<cstdio>

#include<vector>

#include<cstring>

using namespace std;

const int N=3e3+;

int n,m,leaf[N],v[N],dp[N][N];

vector<int> G[N],E[N];

int dfs1(int x) {

    if (G[x].size()==) return leaf[x]=;

    leaf[x]=;

    for (int i=;i<G[x].size();i++) {

        int y=G[x][i];

        leaf[x]+=dfs1(y);

    }

    return leaf[x];

}

void dfs2(int x) {

    if (v[x]) dp[x][]=v[x];

    dp[x][]=;

    for (int i=;i<G[x].size();i++) {

        int y=G[x][i],len=E[x][i];

        dfs2(y);

        for (int j=leaf[x];j;j--)

            for (int k=;k<=leaf[y];k++)

                dp[x][j]=max(dp[x][j],dp[y][k]+dp[x][j-k]-len);

    }

}

int main()

{

    int n,m; cin>>n>>m;

    for (int i=;i<=n-m;i++) {

        int t,x,y; cin>>t;

        for (int j=;j<=t;j++) {

            scanf("%d%d",&x,&y);

            G[i].push_back(x);

            E[i].push_back(y);

        }

    }

    dfs1();

    for (int i=n-m+;i<=n;i++) scanf("%d",&v[i]);

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

    dfs2();

    int ans=;

    for (int i=;i<=leaf[];i++) if (dp[][i]>=) ans=i;

    cout<<ans<<endl;

    return ;

}