hdu4044GeoDefense 树形dp+分组双肩包

//在一颗树上每个点建炮台，
//每个点都有不同价格和威力的炮台选择，每个点只能建一个炮台
//敌人从树根1点出发，走出叶子节点玩家就输了，对于每一个节点，敌人走哪一个子节点不确定
//问给m块钱，问最多能保证能确定挡住hp为多大的敌人
//dp[u][i] 表示第u个节点及其子树分配i块能得到最大的杀伤力
//那么从子节点往上更新时就是一个分组背包
//处理完子节点后u点对于每一个选择也是一个分组背包
//由于会出现price为0的点，那么对于用一维dp会使得在同一点
//选择多个物品，所以需要用一个tmp存下其前面的情况
#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std ;
const int maxn = 1010;
const int inf = 0x7fffffff ;
int dp[maxn][maxn] ;
vector<int> vec[maxn] ;
int c[maxn][maxn] , v[maxn][maxn] ,len[maxn] ;
int tmp[maxn] ;
int vis[maxn] ;
int n , m ;
void debug()
{
    for(int i = 1;i <= n;i++)
    for(int j = 0;j <= m;j++)
    printf("%d%c" ,dp[i][j] , j == m ?'\n':' ');
}
void dfs(int u)
{
    int flag = 0 ;
    for(int i = 0;i < vec[u].size() ;i++)
    {
        int v = vec[u][i] ;
        if(vis[v])continue ;
        vis[v] = 1;
        dfs(v) ;
        if(flag == 0)
        {
            for(int j = 0;j <= m;j++)
            dp[u][j] = dp[v][j] ;
            flag = 1 ;
        }
        else
        for(int j = m;j >= 0;j--)
        {
            int temp = 0 ;
            for(int k = 0;k <= j;k++)
            temp = max(temp , min(dp[v][k] , dp[u][j-k])) ;
            dp[u][j] = temp ;
        }
    }
    for(int i = 0;i <= m;i++)
    tmp[i] = dp[u][i] ;         //处理price为0的情况
    for(int j = m;j >= 0;j--)
    for(int i = 1;i <= len[u] ;i++)
    if(j < c[u][i])continue ;
    else  dp[u][j] = max(dp[u][j] , tmp[j-c[u][i]]+ v[u][i]) ;
}

int main()
{
    //freopen("in.txt" ,"r" ,stdin) ;
    int  t;
    scanf("%d" ,&t) ;
    while(t--)
    {
        scanf("%d" ,&n) ;
        for(int i = 1;i <= n;i++)
        vec[i].clear();
        memset(len , 0 , sizeof(len)) ;
        for(int i = 1;i < n;i++)
        {
            int a , b;
            scanf("%d%d" ,&a , &b) ;
            vec[a].push_back(b) ;
            vec[b].push_back(a) ;
        }
        scanf("%d" ,&m) ;
        for(int i = 1;i <= n;i++)
        {
            scanf("%d" ,&len[i]) ;
            for(int j = 1;j <= len[i] ;j++)
                scanf("%d%d" ,&c[i][j] ,&v[i][j]) ;
        }
        memset(vis , 0 ,sizeof(vis)) ;
        memset(dp , 0 , sizeof(dp)) ;
        vis[1] = 1;
        dfs(1) ;
        cout<<dp[1][m]<<endl;
    }
    return 0 ;
}

/*
1
3
1 3
2 1
40
2 0 20 0 10
2 10 20 30 40
2 30 50 50 30
*/