題意：一棵樹，讓你在規定時間Ｔ內從１號節點走到ｎ號節點，並取得最多的寶藏值。
很容易可以想到一個這樣子的樹形DP，dp[u][t]表示u子樹走t長度的距離時所能獲得的最大價值，然後就是1 到 n的鏈上的每個點來分配容量為T的背包
其實就是一個分組背包了，鏈上的每個點代表每一組，每組中的物品為求得的狀態dp[u][0->t]，每組至少取一個物品
還有一個注意點就是邊權有可能為0，所以在樹形DP轉移的過程中要注意了。
以後還是盡量用tmp變量轉移吧，保險- -
[cpp]
#include<cstdio>
#include<cstring>
#include<set>
#include<string>
#include<iostream>
#include<cmath>
#include<vector>
#include<map>
#include<stack>
#include<time.h>
#include<queue>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn = 110;
#define lowbit(x) ((x)&(-(x)))
#define sqr(x) ((x)*(x))
#define PB push_back
#define MP make_pair
typedef unsigned long long ULL;
typedef long long LL;
typedef vector<int> VI;
typedef vector<string> VS;
typedef pair<int,int> PII;
vector<PII> edge[maxn];
int n,T;
int val[maxn];
int pre[maxn];
bool flag[maxn];
void dfs1(int u,int f)
{
if(u==n)
{
pre[u]=f;
return ;
}
for(int i=0;i<edge[u].size();i++)
{
int v=edge[u][i].first;
if(v==f) continue;
pre[v]=u;
dfs1(v,u);
}
}
int dp[maxn][510];
void Max(int &a,int cmp){
if(cmp>a) a=cmp;
}
void dfs(int u,int f,int T)
{
dp[u][0]=val[u];
for(int i=0;i<edge[u].size();i++)
{
int v=edge[u][i].first;
if(v==f || flag[v]) continue;
int w=edge[u][i].second;
dfs(v,u,T-w);
for(int x=T;x>=0;x--)
{
int tmp=-1;
for(int i=0;i<=x;i++) if(x-i-2*w>=0 && dp[v][x-i-2*w]!=-1 && dp[u][i]!=-1)
{
Max(tmp,dp[u][i]+dp[v][x-i-2*w]);
}
Max(dp[u][x],tmp);
}
}
}
int ans[510];
int mm[maxn][maxn];
int main()
{
int a,b,c;
while(scanf("%d%d",&n,&T)!=EOF)
{
for(int i=1;i<=n;i++) edge[i].clear();
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&a,&b,&c);
edge[a].PB(MP(b,c));
edge[b].PB(MP(a,c));
mm[a][b]=mm[b][a]=c;
}
for(int i=1;i<=n;i++) scanf("%d",&val[i]);
memset(pre,-1,sizeof(pre));
memset(flag,false,sizeof(flag));
dfs1(1,0);
flag[1]=true;
int test=0;
for(int i=n;i!=1;i=pre[i])
{
test+=mm[i][pre[i]];
flag[i]=true;
}
if(test>T)
{
printf("Human beings die in pursuit of wealth, and birds die in pursuit of food!\n");
continue;
}
T-=test;
memset(dp,-1,sizeof(dp));
for(int i=1;i<=n;i++) if(flag[i]) dfs(i,0,T);
memset(ans,-1,sizeof(ans));
ans[0]=0;
for(int i=n;i!=-1;i=pre[i])
{
for(int m=T;m>=0;m--)
{
for(int j=0;j<=m;j++) if(ans[m-j]!=-1 && dp[i][j]!=-1)
{
Max(ans[m],ans[m-j] + dp[i][j]);
}
}
}
int ret=0;
for(int i=0;i<=T;i++) Max(ret,ans[i]);
printf("%d\n",ret);
}
return 0;
}
/*
4 3
1 4 1
4 2 0
2 3 1
10 10 10 10
5 3
1 5 1
5 2 0
2 3 0
3 4 1
10 10 10 10 10
*/
