HDU 4276 The Ghost Blows Light

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 110;
 4 struct arc {
 5     int to,w,next;
 6     arc(int x = 0,int y = 0,int z = -1) {
 7         to = x;
 8         w = y;
 9         next = z;
10     }
11 } e[maxn*maxn];
12 int head[maxn],dp[maxn][510],val[maxn],tot,sum,t,n;
13 void add(int u,int v,int w) {
14     e[tot] = arc(v,w,head[u]);
15     head[u] = tot++;
16 }
17 bool shortest(int u,int fa) {
18     if(u == n) return true;
19     for(int i = head[u]; ~i; i = e[i].next) {
20         if(e[i].to == fa) continue;
21         if(shortest(e[i].to,u)) {
22             sum += e[i].w;
23             e[i].w = e[i^1].w = 0;
24             return true;
25         }
26     }
27     return false;
28 }
29 void dfs(int u,int fa){
30     for(int i = 0; i <= t; ++i) dp[u][i] = val[u];
31     for(int i = head[u]; ~i; i = e[i].next){
32         if(e[i].to == fa) continue;
33         dfs(e[i].to,u);
34         int cost = e[i].w<<1;
35         for(int j = t; j >= cost; --j)
36             for(int k = 0; k + cost <= j; ++k)
37                 dp[u][j] = max(dp[u][j],dp[e[i].to][k] + dp[u][j - cost - k]);
38     }
39 }
40 int main() {
41     int u,v,w;
42     while(~scanf("%d%d",&n,&t)){
43         memset(head,-1,sizeof head);
44         sum = tot = 0;
45         for(int i = 1; i < n; ++i){
46             scanf("%d%d%d",&u,&v,&w);
47             add(u,v,w);
48             add(v,u,w);
49         }
50         memset(dp,0,sizeof dp);
51         for(int i = 1; i <= n; ++i) scanf("%d",val + i);
52         shortest(1,-1);
53         if(sum > t) {
54             puts("Human beings die in pursuit of wealth, and birds die in pursuit of food!");
55             continue;
56         }
57         t -= sum;
58         dfs(1,-1);
59         printf("%d\n",dp[1][t]);
60     }
61     return 0;
62 }