Description：

一棵树，在树上找出一条路径，可以重复经过点和边，每个点有价值和花费时间，每条边有花费时间，问一定时间内的最大价值。

$1\le n \le 300$ $1\le T \le 300$

Solution：

树形 $DP$ 。

$g[i][j]$ 表示从这个点走到子树中走回来， $g[i][j]=max(g[i][k]+g[son][j-k-v\times 2])$

$f[i][j]$ 表示从这个点走到子树中不走回来， $f[i][j]=max(f[i][k]+g[son][j - k - v\times 2],g[i][k]+f[son][j - k - v])$

$h[i][j]$ 表示经过这个点的最长路径， $h[i][j]=max(f[i][k]+f[son][j-k-v],h[i][k]+g[son][j - k - 2\times v],g[i][k]+h[son][j - k - 2\times v])$

注意枚举子树转移前先复制一个版本然后每次按照这个版本转移！！！这样一定万无一失。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,t;

#define MAXN 310

struct edge

{

	int to,nxt,v;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int l)

{

	++edgenum;e[edgenum].to = b;e[edgenum].v = l;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].v = l;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

int w[MAXN],c[MAXN];

typedef long long ll;

ll f[MAXN][MAXN],g[MAXN][MAXN],h[MAXN][MAXN];

ll tmp[MAXN];

bool v[MAXN];

void dp(int k)

{

	v[k] = true;

	for(int i = c[k];i <= t;++i)f[k][i] = g[k][i] = h[k][i] = w[k];

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(v[e[i].to])continue;

		dp(e[i].to);

		for(int j = 0;j <= t;++j)tmp[j] = h[k][j];

		for(int i1 = 0;i1 <= t;++i1)

		{

			for(int i2 = 0;i2 <= t;++i2)

			{

				if(i1 - i2 - e[i].v >= 0)h[k][i1] = max(h[k][i1],f[k][i2] + f[e[i].to][i1 - i2 - e[i].v]);

				if(i1 - i2 - 2 * e[i].v >= 0)h[k][i1] = max(h[k][i1],tmp[i2] + g[e[i].to][i1 - i2 - 2 * e[i].v]);

				if(i1 - i2 - 2 * e[i].v >= 0)h[k][i1] = max(h[k][i1],g[k][i2] + h[e[i].to][i1 - i2 - 2 * e[i].v]);

			}

		}

		for(int j = 0;j <= t;++j)tmp[j] = f[k][j];

		for(int i1 = 0;i1 <= t;++i1)

		{

			for(int i2 = 0;i2 <= t;++i2)

			{

				if(i1 - i2 - 2 * e[i].v >= 0)f[k][i1] = max(f[k][i1],tmp[i2] + g[e[i].to][i1 - i2 - 2 * e[i].v]);

				if(i1 - i2 - e[i].v >= 0)f[k][i1] = max(f[k][i1],g[k][i2] + f[e[i].to][i1 - i2 - e[i].v]);

			}

		}

		for(int j = 0;j <= t;++j)tmp[j] = g[k][j];

		for(int i1 = 0;i1 <= t;++i1)

		{

			for(int i2 = 0;i2 <= t;++i2)

			{

				if(i1 - i2 - 2 * e[i].v >= 0)g[k][i1] = max(g[k][i1],tmp[i2] + g[e[i].to][i1 - i2 - 2 * e[i].v]);

			}

		}

	}

	return;

}

int main()

{

	freopen("toyuq.in","r",stdin);

	freopen("toyuq.out","w",stdout);

	scanf("%d%d",&n,&t);

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

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

	int a,b,l;

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

	{

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

		add(a,b,l);

	}

	memset(f,0xc0,sizeof(f));

	memset(g,0xc0,sizeof(g));

	memset(h,0xc0,sizeof(h));

	memset(v,false,sizeof(v));

	dp(1);

	ll ans = 0;

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

	{

		ans = max(ans,h[i][t]);

	}

	cout << ans << endl;

	fclose(stdin);

	fclose(stdout);

	return 0;

}