hdu1011

发表于 | 分类于 | 阅读数 次

链接:hdu1011

题解

  • 很裸的树形dp,dp[i][j]表示第i个节点去了j个人能拿的最多大脑
  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47

    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #define rep(i,x,y) for(register int i=x;i<=y;++i)
    #define repd(i,x,y) for(register int i=x;i>=y;--i)
    #define ll long long
    using namespace std;
    const int N=300+7;
    int dp[N][N],head[N],nxt[N],to[N],c[N],v[N],vis[N],n,m,cnt;
    inline void adde(int a,int b){
    	to[++cnt]=b;
    	nxt[cnt]=head[a];
    	head[a]=cnt;
    }
    int dfs(int u){
    	vis[u]=1;
    	rep(i,c[u],m)dp[u][i]=v[u];
    	for(int i=head[u],t;i;i=nxt[i])if(!vis[t=to[i]]){
    		dfs(t);
    		repd(i,m,c[u])rep(j,1,i-c[u])if(dp[t][j])dp[u][i]=max(dp[u][i],dp[u][i-j]+dp[t][j]);
    	}
    }
    int main(){
    	while(~scanf("%d%d",&n,&m)&&n!=-1){
    		memset(vis,0,sizeof vis);
    		memset(head,0,sizeof head);
    		memset(dp,0,sizeof dp);
    		cnt=0;
    		rep(i,1,n){
    			scanf("%d%d",&c[i],&v[i]);
    			c[i]=(c[i]+19)/20;
    			//if(c[i]==0)c[i]++;
    		}
    		rep(i,1,n-1){
    			int a,b;
    			scanf("%d%d",&a,&b);
    			adde(a,b);adde(b,a);
    		}
    		dfs(1);
    		printf("%d\n",m==0?0:dp[1][m]);
    	}
    	return 0;
    }