题目大意：在一个n个节点的树形迷宫中，1为起点，n为出口。每个节点上有一定价值的珠宝，在节点之间移动的时间已知，问在能走出迷宫的前提下并且不超过m的时间内能收集的最多珠宝是多少？
题目分析：在树上，从1到n的路径唯一。从1到n的唯一路径叫做主线路，要想走到出口，一定会经过主线路，也就是必须经过主线路上节点。在脱离主线路之前必须要预留出返回的时间。
代码如下：
# include<iostream>
# include<cstdio>
# include<vector>
# include<queue>
# include<cstring>
# include<algorithm>
using namespace std; const int N=105;
const int INF=1000000000; int n,m;
int d[N];
int dp[N][N*5];
int g[N][N];
int w[N],pre[N];
vector<int>e[N]; void init()
{
int a,b,c;
for(int i=1;i<=n;++i)
e[i].clear();
for(int i=1;i<n;++i){
scanf("%d%d%d",&a,&b,&c);
g[a][b]=g[b][a]=c;
e[a].push_back(b);
e[b].push_back(a);
}
for(int i=1;i<=n;++i)
scanf("%d",w+i);
} void spfa()
{
fill(pre,pre+n+1,-1);
fill(d+1,d+n+1,INF);
queue<int>q;
q.push(1);
d[1]=0;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=0;i<e[u].size();++i){
int v=e[u][i];
if(d[v]>d[u]+g[u][v]){
d[v]=d[u]+g[u][v];
pre[v]=u;
q.push(v);
}
}
}
} void dfs(int u,int fa)
{
fill(dp[u],dp[u]+m+1,w[u]);
for(int i=0;i<e[u].size();++i){
int v=e[u][i];
if(v==fa) continue;
dfs(v,u); int t=2*g[u][v]; for(int j=m;j>=t;--j)
for(int k=0;k+t<=j;++k)
dp[u][j]=max(dp[u][j],dp[v][k]+dp[u][j-k-t]);
}
} void solve()
{
spfa();
if(d[n]>m){
printf("Human beings die in pursuit of wealth, and birds die in pursuit of food!\n");
}else{
int u=n;
while(pre[u]!=-1){
g[pre[u]][u]=g[u][pre[u]]=0;
u=pre[u];
}
m-=d[n];
dfs(1,-1);
printf("%d\n",dp[1][m]);
}
} int main()
{
while(~scanf("%d%d",&n,&m))
{
init();
solve();
}
return 0;
}