题意：
n个房间，每个有一定的钱，一个房间到另一个房间花费一定的时间，给你房间连接树，求在t时间内到达房间m能得到的最大钱数（从房间1（根）出发）
分析：
该题关键是最后要到达m，没有这个条件，就是基础的树形背包，哎，一开始没思路，放了一段时间，看看题解才明白，该题突破口，就是，你先想怎么判断不能到到达m的情况，自然想到最短路，对树先求一次最短路，在最短路上的点只能，过一次，其他得点过两次，把最短路上的点花费置零，剩下的就是基础的树形背包。
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <string>
#include <cctype>
#include <complex>
#include <cassert>
#include <utility>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int>p;
typedef long long ll;
#define lson l,m,rt<<1
#define pi acos(-1.0)
#define rson m+1,r,rt<<11
#define All 1,N,1
#define read freopen("in.txt", "r", stdin)
const ll INFll = 0x3f3f3f3f3f3f3f3fLL;
const int INF= <<;
const int mod = ;
int d[],dp[][],head[],n,t,len;
int par[];
struct edge{
int st,en,c,next;
}e[];
void add(int a,int b,int c)
{
e[len].st=a;
e[len].en=b;
e[len].c=c;
e[len].next=head[a];
head[a]=len++;
}
//求最短路
int dijkstra(int s){
priority_queue<p,vector<p>,greater<p> >q;
for(int i=;i<=n;++i)
d[i]=INF;
q.push(p(,s));
d[s]=;
memset(par,-,sizeof(par));
edge a,b;
while(!q.empty()){
p a=q.top();
q.pop();
int j=a.second;
int cost=a.first;
if(d[j]<cost)continue;
for(int i=head[j];i!=-;i=e[i].next){
edge g=e[i];
if(d[g.en]>cost+g.c){
par[g.en]=i;
d[g.en]=cost+g.c;
q.push(p(d[g.en],g.en));
}
}
}
//最短路上的点置零
for(int i=n;i!=s;i=e[par[i]].st){
e[par[i]].c=;
e[par[i]^].c=;
}
return d[n];
}
int used[];
void dfs(int root){
used[root]=;
for(int i=head[root];i!=-;i=e[i].next){
int son=e[i].en;
int cost=e[i].c*;//走两次
if(used[son])continue;
dfs(son);
for(int j=t;j>=cost;--j){
for(int k=;k+cost<=j;++k){
dp[root][j]=max(dp[root][j],dp[root][j-k-cost]+dp[son][k]);
}
}
}
}
int main()
{
int a,b,c;
while(~scanf("%d%d",&n,&t)){
memset(dp,,sizeof(dp));
memset(head,-,sizeof(head));
memset(used,,sizeof(used));
len=;
for(int i=;i<n-;++i){
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
for(int i=;i<=n;++i){
scanf("%d",&dp[i][]);
}
t-=dijkstra();
int maxv=;
if(t<)printf("Human beings die in pursuit of wealth, and birds die in pursuit of food!\n");
else{
dfs();
for(int i=;i<=t;++i)
maxv=max(maxv,dp[][i]);
printf("%d\n",maxv);
}
}
return ;