这题是在一个图中收集点上的价值，树形DP+01背包。题目的意思是在m天内要回到原点，但是按照前m/2天收集，后m/2天原路返回来做结果是对的。用dp[k][i]表示从k点出发，用 i 天能获得的最大值，状态转移方程为 dp[k][a] <?= dp[k][a - w[k][u] - b] + dp[u][b]。意思是总共a天，花了w[k][u]天从k走到u点（k与u相连），用b天从u开始收集，至于剩下的a -w[k][u] -b天可能用不到，就是用来凑数的。
下面的代码很悲剧，时限2000它跑出个2001，因为里面有个错误。更奇葩的是OJ居然不给WA，也不给RE，我很想知道犯了这个错误是怎么还能正常运行同时保证结果正确的。当然了，我是知道这个错误在哪儿的。
1 #include <stdio.h> 2 #include <string.h> 3 const int N = 102; 4 int fst[N],nxt[N],to[N<<1]; 5 int dp[N][N],T[N][N],V[N]; 6 bool vis[N]; 7 int n,m,k; 8 void max(int &a,int b) 9 { 10 if(a < b) a = b; 11 } 12 void dfs(int u) 13 { 14 int i,j,v,e; 15 vis[u] = 1; 16 for(e = fst[u];;e = nxt[e]) 17 { 18 if(e == -1) return ; 19 v = to[e]; 20 if(!vis[v]) 21 { 22 dfs(v); 23 for(i = m; i >= T[u][v]; i--) 24 for(j = 0; j <= i-T[u][v]; j++) 25 max(dp[u][i],dp[u][i-T[u][v]-j]+dp[v][j]); 26 } 27 } 28 } 29 int main() 30 { 31 int u,v,w,i,j; 32 while(~scanf("%d",&n)) 33 { 34 memset(fst,-1,sizeof fst); 35 memset(vis,0,sizeof vis); 36 for(i = 1; i <= n; i++) 37 scanf("%d",&V[i]); 38 for(i = j = 1; i < n; i++) 39 { 40 scanf("%d%d%d",&u,&v,&w); 41 T[u][v] = T[v][u] = w; 42 nxt[j] = fst[u]; 43 to[j] = v; 44 fst[u] = j++; 45 nxt[j] = fst[v]; 46 to[j] = u; 47 fst[v] = j++; 48 } 49 scanf("%d%d",&k,&m); 50 m /= 2; 51 for(i = 1; i <= n; i++) 52 for(j = 0; j <= m; j++) 53 dp[i][j] = V[i]; 54 dfs(k); 55 printf("%d\n",dp[k][m]); 56 } 57 return 0; 58 }