HDU-4044 树形背包dp好题

不会做，题解是参考网上的。感觉这道题是到好题，使得我对树形背包dp更了解了。

有几个注意的点，直接给出代码，题解以及注意点都在注释里了。

#include<bits/stdc++.h>

using namespace std;

const int N=1e3+;

const int INF=0x3f3f3f3f;

int n,m,dp[N][N],p[N][N];

vector<int> G[N],P1[N],P2[N];

//对于背包问题，有代价为0的物品麻烦在于：状态转移时候还跟自己状态有关，所以本次状态先还不能改变，要用tmp先记录，转移完后才能改变

void dfs(int x,int fa) {

    dp[x][]=INF;

    //不建炮台的情况：分组背包（每个儿子就是一组背包，每组只能选一个物品）

    for (int i=;i<G[x].size();i++) {  //一组物品

        int y=G[x][i];

        if (y==fa) continue;

        dfs(y,x);

        for (int j=m;j>=;j--) {  //容量

            int tmp=;

            for (int k=;k<=j;k++)  //该组物品个数

                tmp=max(tmp,min(dp[y][k],dp[x][j-k]));

            dp[x][j]=tmp;

        }

    }

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

    //建炮台情况：注意只能建一个炮台

    for (int i=m;i>=;i--) {

        int tmp=dp[x][i];  //tmp是为了防止存在造价为0的炮台，否则直接用dp[x][i]会使得建立多个炮台

        for (int j=;j<P1[x].size();j++)

            if (i>=P1[x][j])

            tmp=max(tmp,dp[x][i-P1[x][j]]+P2[x][j]);

        dp[x][i]=tmp;

    }

}

int main()

{

    int T; cin>>T;

    while (T--) {

        cin>>n;

        for (int i=;i<=n;i++) G[i].clear(),P1[i].clear(),P2[i].clear();

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

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

            G[x].push_back(y);

            G[y].push_back(x);

        }

        cin>>m;

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

            int l; scanf("%d",&l);

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

                int t1,t2; scanf("%d%d",&t1,&t2);

                P1[i].push_back(t1);

                P2[i].push_back(t2);

            }

        }

        memset(dp,,sizeof(dp));

        dfs(,);

        cout<<dp[][m]<<endl;

    }

    return ;

}