网上题解都是用spfa求1-n路径的，但其实dfs一次就可以了。。
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <iomanip> using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define maxn 1000005
#define MOD 1000000007
#define mem(a , b) memset(a , b , sizeof(a))
#define LL long long
#define INF 100000000 int n , t;
struct edge
{
int u , v , w;
int next;
}E[*];
int head[];
int dp[][];
int val[];
int cost[] , per[];
int id,sum ,flag ; void add(int u , int v , int w)
{
E[id].u = u;
E[id].v = v;
E[id].w = w;
E[id].next = head[u];
head[u] = id++;
}
/*
void spfa()
{
mem(per , -1);
for(int i = 2 ; i <= n ; i ++) cost[i] = INF;
cost[1] = 0;
queue<int>q;
q.push(1);
while(!q.empty())
{
int u = q.front();
q.pop();
for(int i = head[u] ; i >= 0 ; i = E[i].next)
{
if(cost[E[i].v] > cost[u] + E[i].w)
{
cost[E[i].v] = cost[u] + E[i].w;
per[E[i].v] = i;
q.push(E[i].v);
}
}
}
for(int i = 1 ; i <= n ; i ++) cout << per[i] << endl;
for(int i = per[n] ; i >= 0 ; i = per[i])
{
cout << E[i].u << " " << E[i].v << " " << E[i].w << endl;
E[i].w = 0;
}
}*/
/*
bool judge(int u,int pre)///找出1~n的路径
{
if(u == n)return true;
for(int i = head[u]; i != -1 ; i = E[i].next)
{
int v = E[i].v;
if(v == pre)continue;
if(judge(v,u))
{
sum += E[i].w;
E[i].w=0;
return true;
}
}
return false;///这句话必须有，因为这一句我没写WA到死.....
}
*/ int judge(int u , int per)
{
int flag=;if(u==n)return ;
for(int i = head[u] ; i >= ; i = E[i].next )
{
if(E[i].v == per) continue;
if(judge(E[i].v,u)) {sum += E[i].w ; E[i].w = ; flag = ;}
else E[i].w*=;
}
return flag;
} void solve(int u , int per)
{
for(int i = head[u] ; i >= ; i = E[i].next)
{
if(E[i].v == per) continue;
solve(E[i].v , u);
for(int j = t ; j >= E[i].w ; j --)
{
int up = j - E[i].w;
for(int k = ; k <= up ; k ++)
{
// if(dp[u][up-k] != -1 && dp[E[i].v][k] != -1)
dp[u][j] = max(dp[u][j] , dp[u][up-k] + dp[E[i].v][k]);
}
}
}
} int main()
{
while(scanf("%d %d" , &n , &t) != EOF)
{
mem(dp , );id = ;
mem(head , -);
int u , v , w;
for(int i = ; i < n ; i ++)
{
scanf("%d %d %d" , &u , &v , &w);
//if(u > v) swap(u , v);
add(u , v , w);
add(v , u , w);
}
for(int i = ; i <= n ; i ++)
{
scanf("%d" , &val[i]);
for(int j = ; j <= t ; j ++) dp[i][j] = val[i];
}
flag = sum = ;
judge( , -);
//spfa();
if(sum > t)
{
printf("Human beings die in pursuit of wealth, and birds die in pursuit of food!\n");
continue;
}
//cout << sum << endl;
t -= sum;
solve( , -);
printf("%d\n" , dp[][t]);
}
}