思路：先dfs一下，找出1，n间的路径长度和价值，回溯时将该路径长度和价值清零。那么对剩下的图就可以直接树形dp求解了。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#define inf 100000000
#define Maxn 110
using namespace std;
int vi[Maxn],head[Maxn],dp[Maxn][],e,n,T,a[Maxn],len,sum;
struct Edge{
int u,v,next,val;
}edge[Maxn*];
void init()
{
memset(vi,,sizeof(vi));
memset(head,-,sizeof(head));
memset(dp,,sizeof(dp));
memset(a,,sizeof(a));
e=len=sum=;
}
void add(int u,int v,int val)
{
edge[e].u=u,edge[e].v=v,edge[e].val=val,edge[e].next=head[u],head[u]=e++;
edge[e].u=v,edge[e].v=u,edge[e].val=val,edge[e].next=head[v],head[v]=e++;
}
int dfs(int u)
{
int i,v;
vi[u]=;
if(u==)
{
sum+=a[u];
a[u]=;
return ;
}
for(i=head[u];i!=-;i=edge[i].next)
{
v=edge[i].v;
if(vi[v]) continue;
if(dfs(v))
{
len+=edge[i].val,edge[i].val=edge[i^].val=;
sum+=a[u];
a[u]=;
return ;
}
}
return ;
}
void Treedp(int u)
{
int i,v,j,k;
vi[u]=;
for(i=head[u];i!=-;i=edge[i].next)
{
v=edge[i].v;
if(vi[v]) continue;
Treedp(v);
int cost=*edge[i].val;
for(j=T;j>=cost;j--){
int temp=;
for(k=;k<=j-cost;k++)
temp=max(temp,dp[u][j-cost-k]+dp[v][k]);
dp[u][j]=max(dp[u][j],temp);
} }
for(i=;i<=T;i++)
dp[u][i]+=a[u];
}
int main()
{
int i,j,u,v,t;
while(scanf("%d%d",&n,&T)!=EOF)
{
init();
for(i=;i<n;i++){
scanf("%d%d%d",&u,&v,&t);
add(u,v,t);
}
for(i=;i<=n;i++)
scanf("%d",a+i);
dfs(n);
if(len>T)
{
printf("Human beings die in pursuit of wealth, and birds die in pursuit of food!\n");
continue;
}
T-=len;
memset(vi,,sizeof(vi));
Treedp(n);
printf("%d\n",dp[n][T]+sum);
}
return ;
}