题目大概说一棵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路径上的点本身就是父子关系。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 #define MAXN 111 6 struct Edge{ 7 int v,w,next; 8 }edge[MAXN<<1]; 9 int NE,head[MAXN]; 10 void addEdge(int u,int v,int w){ 11 edge[NE].v=v; edge[NE].w=w; edge[NE].next=head[u]; 12 head[u]=NE++; 13 } 14 int n,t,val[MAXN],d[MAXN][555],par[MAXN],weight[MAXN]; 15 bool dp(int u){ 16 bool flag=0; 17 d[u][0]=val[u]; 18 for(int i=head[u]; i!=-1; i=edge[i].next){ 19 int v=edge[i].v; 20 if(v==par[u]) continue; 21 par[v]=u; 22 weight[v]=edge[i].w; 23 if(dp(v)){ 24 flag=1; 25 continue; 26 } 27 for(int j=t; j>=0; --j){ 28 for(int k=0; ; ++k){ 29 if(edge[i].w*2+k>j) break; 30 if(d[v][k]==-1 || d[u][j-edge[i].w*2-k]==-1) continue; 31 d[u][j]=max(d[u][j],d[u][j-edge[i].w*2-k]+d[v][k]); 32 } 33 } 34 } 35 if(u==n) return 1; 36 return flag; 37 } 38 int rec[MAXN],rn,tot; 39 void dfs(int u){ 40 if(u!=1){ 41 tot+=weight[u]; 42 dfs(par[u]); 43 } 44 rec[rn++]=u; 45 } 46 int ans[MAXN][555]; 47 int main(){ 48 int a,b,c; 49 while(~scanf("%d%d",&n,&t)){ 50 NE=0; 51 memset(head,-1,sizeof(head)); 52 for(int i=1; i<n; ++i){ 53 scanf("%d%d%d",&a,&b,&c); 54 addEdge(a,b,c); 55 addEdge(b,a,c); 56 } 57 for(int i=1; i<=n; ++i) scanf("%d",val+i); 58 memset(d,-1,sizeof(d)); 59 dp(1); 60 rn=tot=0; 61 dfs(n); 62 tot=t-tot; 63 memset(ans,-1,sizeof(ans)); 64 for(int i=0; i<=tot; ++i) ans[0][i]=d[rec[0]][i]; 65 for(int i=1; i<rn; ++i){ 66 for(int j=0; j<=tot; ++j){ 67 for(int k=0; k<=tot; ++k){ 68 if(j+k>tot || ans[i-1][j]==-1 || d[rec[i]][k]==-1) continue; 69 ans[i][j+k]=max(ans[i][j+k],ans[i-1][j]+d[rec[i]][k]); 70 } 71 } 72 } 73 int res=-1; 74 for(int i=0; i<=tot; ++i) res=max(res,ans[rn-1][i]); 75 if(res==-1) puts("Human beings die in pursuit of wealth, and birds die in pursuit of food!"); 76 else printf("%d ",res); 77 } 78 return 0; 79 }