学步园

题意：

n 个点 maxtime的时间

下面给定一棵树及走过该边需要的时间

最后一行给定 每个点的宝藏价值

问在maxtime时间内能否 从 1->n ，若能输出最多能获得的宝藏价值

思路：

对于树，除了1->n的路径， 若去其他点则要走回头路

所以我们可以先走到终点， 最后时间 - 1-n路径花费的时间， 再把该路径的边花费改为0

这样就是 剩下时间 ，走非路径上点 能获得的最高价值，就是背包问题

dp[i][j] 表示 i 点用了  j 时刻能获得的最大价值

先用spfa跑出1-n的路径，再修改路径上的边权， 树形背包一下 结果就是 dp[1][maxtime]

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string>
#include<queue>
#include<string.h>
#include<map>
#include<set>
#include<stack>
#include<vector>
#include<math.h>
#define inf 10000000
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define Mid(x,y) ((x+y)>>1)
#define ll int
using namespace std;
inline ll Min(ll a,ll b){return a>b?b:a;}
inline ll Max(ll a,ll b){return a<b?b:a;}
#define N 105
struct Edge{
	int from, to, dis, nex;
}edge[N<<1];
int head[N], edgenum;
void addedge(int u, int v, int d){
	Edge E={u, v, d, head[u]};
	edge[ edgenum ] = E;
	head[u] = edgenum++;
}
int maxtime, n, a[N];
int pre[N], dis[N];
void spfa(){
	queue<int>q;
	q.push(1);
	memset(dis, -1, sizeof(dis));
	dis[1] = 0;
	pre[1] = -1;
	while(!q.empty()){
		int u = q.front(); q.pop();
		for(int i = head[u]; i !=-1;i = edge[i].nex){
			int v = edge[i].to;
			if(dis[v] == -1)
			{
				dis[v] = dis[u] + edge[i].dis;
				pre[v] = u;
				q.push(v);
			}
		}
	}
}
int dp[N][505];
void dfs(int u, int fa){
	for(int i = 0;i <= maxtime; i++)dp[u][i] = a[u];
	for(int i = head[u]; ~i; i =edge[i].nex)
	{
		int v = edge[i].to;
		if(v != fa)
		{
			dfs(v, u);
			int cost = edge[i].dis<<1;
			for(int j = maxtime; j>= cost; j--)
			{
				for(int k = 0; k<= j - cost; k++)
					dp[u][j] = Max(dp[u][j], dp[v][k] + dp[u][j-cost-k]);
			}
		}
	}
}
bool Islian[N];

int main(){
	ll i, u, v, d, j;

	while(~scanf("%d %d",&n,&maxtime)){
		memset(Islian, 0, sizeof(Islian));
		memset(head, -1, sizeof(head)); edgenum = 0;
		memset(dp, 0, sizeof(dp));

		for(i=1;i<n;i++){
			scanf("%d %d %d",&u,&v,&d);
			addedge(u, v, d);
			addedge(v, u, d);
		}
		for(i=1;i<=n;i++)scanf("%d",&a[i]);

		spfa();
		if(dis[n] == -1 || dis[n]>maxtime)
		{printf("Human beings die in pursuit of wealth, and birds die in pursuit of food!\n");continue;}
		i = n;
		while(i!=-1)
		{
			Islian[i] = true;
			i = pre[i];
		}
		i = n;
		while(i!=-1)
		{
			for(j=head[i];j!=-1;j=edge[j].nex)
				if(Islian[ edge[j].to ])
					edge[j].dis = 0;
			i = pre[i];
		}

		maxtime -= dis[n];
		dfs(1,-1);
		printf("%d\n",dp[1][maxtime]);
	}
	return 0;
}