C++11(clang++ 3.9) 解法, 执行用时: 35ms, 内存消耗: 760K, 提交时间: 2019-10-26 16:19:19

#include<bits/stdc++.h>
#define M 305
using namespace std;
int n,T,A[M],dp[M][M];
bool in[M];
struct hzl {
	int a,b;
};
vector<hzl>E[M];
void dfs(int x,int f,int d) {
	if(d>T)return;
//	printf("%d\n",x);
	dp[x][0]=A[x];
	int now=T-d;
	for(int i=0; i<E[x].size(); i++) {
		int v=E[x][i].a;
		if(v==f)continue;
		dfs(v,x,d+E[x][i].b);
//		printf("%d %d %d\n",x,now,E[x][i].b);
		for(int a=now; a>=E[x][i].b; a--)
			for(int b=0; b<=a-E[x][i].b; b++)
			dp[x][a]=max(dp[x][a],dp[x][a-b-E[x][i].b]+dp[v][b]);
	}
	for(int i=1; i<=now; i++)dp[x][i]=max(dp[x][i],dp[x][i-1]);
	return ;
}
int main() {
	scanf("%d%d",&n,&T);
	for(int i=1; i<=n; i++)scanf("%d",&A[i]);
	for(int i=2; i<=n; i++) {
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		E[x].push_back((hzl) {
			y,z
		});
//		E[y].push_back((hzl) {
//			x,z
//		});
		in[y]=1;
	}
	for(int i=1; i<=n; i++)
		if(!in[i]) {
			dfs(i,0,0);
			printf("%d\n",dp[i][T]);
		}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 30ms, 内存消耗: 608K, 提交时间: 2019-10-29 11:26:39

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,t;
int head[310],to[310],ne[310],w[310],cnt=0;
void add(int u,int v,int val){
	cnt++;
	to[cnt]=v;
	w[cnt]=val;
	ne[cnt]=head[u];
	head[u]=cnt;
}
int v[310];
int f[310][310]={0};
void dfs(int r,int tt){
	if(tt<0)return;
	for(int i=head[r];i!=-1;i=ne[i]){
		dfs(to[i],tt-w[i]);
		for(int j=tt;j>=w[i];j--){
			for(int k=w[i];k<=j;k++){
				f[r][j]=max(f[r][j],f[r][j-k]+f[to[i]][k-w[i]]+v[to[i]]);
			}
		}
	}
}
bool vis[310]={0};
int main(){
	memset(head,-1,sizeof(head));
	scanf("%d%d",&n,&t);
	for(int i=1;i<=n;i++)scanf("%d",&v[i]);
	for(int i=1;i<=n-1;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
		vis[y]=1;
	}
	int root; 
	for(int i=1;i<=n;i++){
		if(vis[i]==0){
			root=i;
			break;
		}
	}
	dfs(root,t);
	f[root][t]+=v[root];
	printf("%d",f[root][t]);
	return 0;
}