<span style="font-family: Arial, Helvetica, sans-serif; background-color: rgb(255, 255, 255);"><span style="font-size:14px;">题意：给你n个点，n-1条边构成树，每条边有边树，每个点有点权（表示走每条边的时间），问在时间T从点1走到点n，能够得到最多的点权有多少。</span></span>首先我们至少要保证1到n的最短路在时间内，此时用spfa，其次，在最优的情况下，最短路径上的边只会经过一次，而其他边会经过两次，对于最短路上的边，spfa走的时候记录权值，然后赋值为0就可以了。对于其他边就可以跑树形dp了。
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 5e4+7;
int dp[111][555],head[111],v[111],d[111],t[111],num,n,kk;
struct list1 {int u,v,w,next;}a[222];
void add(int u,int v,int w) {a[num]={u,v,w,head[u]};head[u]=num++;}
void spfa()
{int i;int pre[111];memset(pre,-1,sizeof(pre));memset(v,0,sizeof(v));memset(d,INF,sizeof(d));queue<int>q;q.push(1);v[1]=1;d[1]=0;while(!q.empty()){int u=q.front();q.pop();v[u]=0;for(i=head[u];~i;i=a[i].next){int u=a[i].u;if(d[u]+a[i].w<d[a[i].v]){pre[a[i].v]=i;d[a[i].v]=d[u]+a[i].w;if(!v[a[i].v]) q.push(a[i].v),v[a[i].v]=1;}}}for(i=n;i!=1;i=a[pre[i]].u){a[pre[i]].w=0;a[pre[i]^1].w=0;}
}
void dfs(int x,int fa)
{for(int i=head[x];~i;i=a[i].next){int u=a[i].v,w=2*a[i].w;if(u==fa) continue;dfs(u,x);for(int j=kk;j>=w;j--)for(int k=0;k<=j-w;k++)dp[x][j]=max(dp[x][j],dp[x][j-k-w]+dp[u][k]);}
}
int main()
{int i,x,y,z;while(~scanf("%d%d",&n,&kk)){memset(dp,0,sizeof(dp));num=0;memset(head,-1,sizeof(head));for(i=1;i<n;i++){scanf("%d%d%d",&x,&y,&z);add(x,y,z);add(y,x,z);}for(i=1;i<=n;i++){scanf("%d",&dp[i][0]);for(int j=0;j<=kk;j++)dp[i][j]=dp[i][0];}if(n==1) {printf("%d\n",dp[1][0]);continue;}spfa();kk-=d[n];if(kk<0) printf("Human beings die in pursuit of wealth, and birds die in pursuit of food!\n");else dfs(1,0),printf("%d\n",dp[1][kk]);}return 0;
}