题目大概说一棵n个结点树，每个结点都有宝藏，走过每条边要花一定的时间，现在要在t时间内从结点1出发走到结点n，问能获得最多的宝藏是多少。
放了几天的题，今天拿出来集中精力去想，还是想出来了。
首先，树上任意两点间最短的那条路径是唯一的，且不管怎么走一定都会走过那条路径上的所有点，也就是说整个行程可以看成两部分组成：一部分就是1到n的最短路径，另一部分就是从这个路径上的某点出发绕回该点的路径。
这样问题就清晰了，现在关键在求第二部分：
- 先用树上背包求出：dp[u][t]，表示从在以u点为根的子树中从u点出发且不经过n结点及其祖先结点最后回到u点总共用时t能获得最多的宝藏
- 最后从1到n最短的那条路径上的各个点u看作物品，有t种规格的体积，每种体积价值是dp[u][t]，背包容量为总时间-走那条最短路所需时间，这样再做一次背包，求出装满某体积（用某时间）能得到的最大价值就OK了。
- 注意的是那个状态是不经过n结点及其祖先结点，这是为了不重复统计，1到n路径上的点本身就是父子关系。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 111
struct Edge{
int v,w,next;
}edge[MAXN<<];
int NE,head[MAXN];
void addEdge(int u,int v,int w){
edge[NE].v=v; edge[NE].w=w; edge[NE].next=head[u];
head[u]=NE++;
}
int n,t,val[MAXN],d[MAXN][],par[MAXN],weight[MAXN];
bool dp(int u){
bool flag=;
d[u][]=val[u];
for(int i=head[u]; i!=-; i=edge[i].next){
int v=edge[i].v;
if(v==par[u]) continue;
par[v]=u;
weight[v]=edge[i].w;
if(dp(v)){
flag=;
continue;
}
for(int j=t; j>=; --j){
for(int k=; ; ++k){
if(edge[i].w*+k>j) break;
if(d[v][k]==- || d[u][j-edge[i].w*-k]==-) continue;
d[u][j]=max(d[u][j],d[u][j-edge[i].w*-k]+d[v][k]);
}
}
}
if(u==n) return ;
return flag;
}
int rec[MAXN],rn,tot;
void dfs(int u){
if(u!=){
tot+=weight[u];
dfs(par[u]);
}
rec[rn++]=u;
}
int ans[MAXN][];
int main(){
int a,b,c;
while(~scanf("%d%d",&n,&t)){
NE=;
memset(head,-,sizeof(head));
for(int i=; i<n; ++i){
scanf("%d%d%d",&a,&b,&c);
addEdge(a,b,c);
addEdge(b,a,c);
}
for(int i=; i<=n; ++i) scanf("%d",val+i);
memset(d,-,sizeof(d));
dp();
rn=tot=;
dfs(n);
tot=t-tot;
memset(ans,-,sizeof(ans));
for(int i=; i<=tot; ++i) ans[][i]=d[rec[]][i];
for(int i=; i<rn; ++i){
for(int j=; j<=tot; ++j){
for(int k=; k<=tot; ++k){
if(j+k>tot || ans[i-][j]==- || d[rec[i]][k]==-) continue;
ans[i][j+k]=max(ans[i][j+k],ans[i-][j]+d[rec[i]][k]);
}
}
}
int res=-;
for(int i=; i<=tot; ++i) res=max(res,ans[rn-][i]);
if(res==-) puts("Human beings die in pursuit of wealth, and birds die in pursuit of food!");
else printf("%d\n",res);
}
return ;
}