ZOJ 3626 Treasure Hunt I （树形DP，常规）

题意：给一棵树，一个人站在节点s，他有m天时间去获取各个节点上的权值，并且最后需要回到起点s，经过每条边需要消耗v天，问最少能收获多少权值？

思路：　　常规的，注意还得跑回原地s。

 //#include <bits/stdc++.h>

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <map>

 #include <algorithm>

 #include <vector>

 #include <iostream>

 #define pii pair<int,int>

 #define INF 0x3f3f3f3f

 #define LL  long long

 using namespace std;

 const int N=;

 int w[N], head[N], dp[N][N], edge_cnt, n;

 struct node

 {

     int from,to,cost,next;

     node(){};

     node(int from,int to,int cost,int next):from(from),to(to),cost(cost),next(next){};

 }edge[N*];

 void add_node(int from,int to,int cost)

 {

     edge[edge_cnt]=node(from,to,cost,head[from]);

     head[from]=edge_cnt++;

 }

 void DFS(int t,int far,int m)

 {

     for(int j=m; j>=; j--) dp[t][j]=w[t];  //本节点的权值

     node e;

     for(int i=head[t]; i!=-; i=e.next)

     {

         e=edge[i];

         if(e.to!=far && m-*e.cost>=)

         {

             DFS(e.to, t, m-*e.cost);

             for(int j=m; j>; j--)

                 for(int k=*e.cost; k<=j; k++)  //给孩子k-2*cost天

                     dp[t][j]=max(dp[t][j], dp[t][j-k]+dp[e.to][k-*e.cost]);

         }

     }

 }

 int main()

 {

     //freopen("input.txt", "r", stdin);

     int a, b, c, s, m;

     while(~scanf("%d",&n))

     {

         memset(head, -, sizeof(head));

         memset(dp, , sizeof(dp));

        edge_cnt=;

         for(int i=; i<=n; i++) scanf("%d",&w[i]);

         for(int i=; i<n; i++)

         {

             scanf("%d%d%d",&a,&b,&c);

             add_node(a,b,c);

             add_node(b,a,c);

         }

         scanf("%d%d",&s,&m);

         DFS(s,-,m);

         printf("%d\n",dp[s][m]);

     }

     return ;

 }

AC代码