学步园

n个点各有权值val [ i ]， 总时间为T，n-1条双向边，u->v，从u走到v 花费为w， 求在花费不超过T的情况下，能获得的经过的各点权值之和最大。

分析：首先预处理出一条从点1 ~ N的最短路， 那么最优路径的主干一定是经过该最短路的。然后是否走其他的点取决于是否有多出的时间（很显然。）。而且经过最短路之外的点的话，那些点要么不走要么走且只走两次（来回）。

所以先预处理出一条最短路之后，最短路上的点权值改为0，然后用树形dp解决是否要取旁边的点。设dp [ u ][ j ]为走到 u 时花费为 j ，那么

dp[u][j] = max(dp[u][j], dp[v][k] + dp[u][j - weit - k]);

完整代码如下：

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>

#define N 105

using namespace std;

int a[N];

struct node{
    int to, nxt, cost;
}edge[N * 3];

int head[N];

int dp[N][N * 5];

int cnt;
int n, t;
int tt;

void init()
{
    cnt = 0;
    memset(head, -1, sizeof(head));
}

void addedge(int u, int v, int w)
{
    edge[cnt].to = v;
    edge[cnt].cost = w;
    edge[cnt].nxt = head[u];
    head[u] = cnt++;
}

int dfs1(int u, int pre)
{
    if(u == n)
    {
        return 1;
    }
    for( int i = head[u]; ~i; i = edge[i].nxt )
    {
        int v = edge[i].to;
        if(v == pre)
            continue;
        if(dfs1(v, u))
        {
            tt += edge[i].cost;
            edge[i].cost = 0;
            return 1;
        }
    }
    return 0;
}

void dfs2(int u, int pre)
{
    for(int i = 0; i <= t; i++)
        dp[u][i] = a[u];
    for( int i = head[u]; ~i; i = edge[i].nxt )
    {
        int v = edge[i].to;
        if(v == pre)
            continue;
        dfs2(v, u);
        int weit = edge[i].cost * 2;
        for(int j = t; j >= weit; j--)
            for(int k = 0; k <= j - weit; k++)
                dp[u][j] = max(dp[u][j], dp[v][k] + dp[u][j - weit - k]);
    }
}

int main()
{
    while(~scanf("%d%d", &n, &t))
    {
        init();
        for(int i = 1; i < n; i++)
        {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            addedge(u, v, w);
            addedge(v, u, w);
        }
        for(int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        tt = 0;
        dfs1(1, -1);
        if(tt > t)
        {
            puts("Human beings die in pursuit of wealth, and birds die in pursuit of food!");
            continue;
        }
        t -= tt;
        dfs2(1, -1);
        printf("%d\n", dp[1][t]);
    }
    return 0;
}