题意：n个点每个点有点权表示宝物的价值。n-1条边，边权表示走这条边需要花的时间。
如果T时间内不能从1走到n，那么就输出字符串。如果能走出，问在T时间内走出能获得的
最大价值。
分析：
先找到1-n的最短路径，并且计算走这条最短路径所需的时间（最短时间)time1，将路径上的边权置0。
如果time1已经超过了T，说明它不能在T时间内走出来。
如果time1<T，那么将剩余的时间看成背包容积，进行树上背包。
dp[i][j]表示从i点出发回到i点，用了时间j获得的最大价值。
dp[s][j]=max(dp[s][j],dp[s][j-k-tmp]+dp[vv][k] （vv为s的儿子)
最短路径上的边只经过一次，其他的边要经过两次。tmp=edge*2；
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int dp[110][510],head[110],v[110];
int T,tot,n,time1;
struct node
{
int val,to;
int next;
}edge[220];
int maxx(int a,int b)
{
return a>b?a:b;
}
void init()
{
memset(dp,0,sizeof(dp));
memset(head,-1,sizeof(head));
tot=0;
}
void add(int a,int b,int c)
{
edge[tot].to=b;
edge[tot].val=c;
edge[tot].next=head[a];
head[a]=tot++;
edge[tot].to=a;
edge[tot].val=c;
edge[tot].next=head[b];
head[b]=tot++;
}
bool dfs1(int u,int pre)
{
if(u==n) return true;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(v==pre) continue;
if(dfs1(v,u))
{
time1+=edge[i].val;
edge[i].val=0;
return true;
}
}
return false;
}
void dfs2(int u,int pre)
{
for(int i=T;i>=0;i--)
dp[u][i]+=v[u];
for(int i=head[u];i!=-1;i=edge[i].next)
{
int vv=edge[i].to;
if(vv==pre) continue;
dfs2(vv,u);
int tmp=edge[i].val*2;
for(int j=T;j>=tmp;j--)
{
for(int k=0;k<=j-tmp;k++)
dp[u][j]=maxx(dp[u][j],dp[vv][k]+dp[u][j-k-tmp]);
}
}
}
int main()
{
int a,b,c;
while(scanf("%d%d",&n,&T)!=EOF)
{
init();
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
for(int i=1;i<=n;i++)
scanf("%d",&v[i]);
time1=0;
dfs1(1,-1);
if(time1>T)
{
printf("Human beings die in pursuit of wealth, and birds die in pursuit of food!\n");
continue;
}
T-=time1;
dfs2(1,-1);
printf("%d\n",dp[1][T]);
}
return 0;
}