做题感悟：这题和昨天那题很像，又用昨天的方法果断超时，然后就……
解题思路：
动态方程：dp[ u ] [ j ] = max ( dp [ u ] [ j ] , dp[ u ] [ j - k - w[u][v] ] + dp[ v ] [ k ] )（u 与 v 相连） dp [ u ] [ j ]代表以 u 为子树时花费为 j 的时间所获得的最大价值， dp[ u ] [ j - k - w[u][v] ] + w[ v ] [ k ]
， 代表以 u 为子树花费时间为 j - k - w[u][v] 所得到的最大价值+ 以 v 为子树花费为 k 的时间（不断枚举时间，w[u][v] 为 u 到 v 的花费的时间）。因为最终要走到原点，so ~> 时间Time = Time/2 ; 这题感觉和记忆话搜素差不多。
代码：
#include<stdio.h>
#include<iostream>
#include<map>
#include<stack>
#include<string>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std ;
#define lld __int64
#define pret(a,b) memset(a,b,sizeof(a))
const double PI = 3.1415926 ;
const double esp = 1e-7 ;
const int INF = 999999999 ;
const int mod = 1000000007 ;
const int MX = 515 ;
int Time,n,S ;
int dp[MX][MX],g[MX][MX],w[MX] ;
bool vis[MX] ;
vector<int>G[MX] ;
void dfs(int u)
{
vis[u]=true ;
dp[u][0]=w[u] ; // 在 u 子树根节点
int num=G[u].size() ;
for(int i=0 ;i<num ;i++)
{
int v=G[u][i] ;
if(!vis[v])
{
dfs(v) ; // 先得到 v 子树
for(int j=Time ;j>=0 ;j--) // 总时间为 Time
for(int k=0 ;k<=j-g[u][v] ;k++) // k 为 v 子树所用时间
dp[u][j]=max(dp[u][j],dp[u][j-k-g[u][v]]+dp[v][k]) ;
}
}
}
void init() // 初始化
{
for(int i=0 ;i<=n ;i++)
G[i].clear() ;
memset(dp,0,sizeof(dp)) ;
}
int main()
{
//freopen("1.txt","r",stdin) ;
int u,v,wx ;
while(~scanf("%d",&n))
{
init() ;
for(int i=1 ;i<=n ;i++)
scanf("%d",&w[i]) ;
for(int i=0 ;i<n-1 ;i++)
{
scanf("%d%d%d",&u,&v,&wx) ;
G[u].push_back(v) ;
G[v].push_back(u) ;
g[u][v]=g[v][u]=wx ;
}
scanf("%d%d",&S,&Time) ;
Time= Time/2 ; // 因为要回到原点
memset(vis,false,sizeof(vis)) ;
dfs(S) ;
int ans=0 ;
for(int i=0 ;i<=Time ;i++) // 找最大的时间
if(dp[S][i]>ans)
ans=dp[S][i] ;
printf("%d\n",ans) ;
}
return 0 ;
}