Description：

给一棵树，每个点出售互不相同的物品，物品有库存，价值和价格，要求买物品必须买一整个联通块，给 $m$ 元求能买到的最大价值。

$1\leqslant n\leqslant 400,1\leqslant m\leqslant 4000$

Solution：

首先直接树形 $DP$ 复杂度肯定是过不了的。

既然要选的是一整个联通块，那么我们就可以枚举每个点作为根节点，然后这个限制就变成了依赖关系，即选了他就必须选他的父亲，那么就可以这样树形 $DP$ 。

但是这样复杂度会变成 $O(nm^2)$ ，还是通过不了，但是我们发现如果这个点不选的话，那么原树会分成几个部分，那么就可以分治下去做，这让我们想到点分治，可以优化成 $O(m^2\log n\log d)$ （二进制分组求多重背包）。但是这样还是通过不了，原因在于多重背包不满足 $O(n^2)$ ，也就是说很大一部分时间都花在了合并背包上。

但是树形 $DP$ 还有一种写法，那就是在序列上倒着 $DP$ ，每次选择跳过一棵子树或者从下一个转移过来，这样的 $DP$ 只有单点插入的复杂度，不用合并背包，复杂度 $O(nm\log n\log d)$ 可以通过。

注意用这种方法 $DP$ 必须保证在子树不选的时候他也不选，也就是说从 $i+1$ 转移过来时必须至少选一个。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 510

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

int val[MAXN],pri[MAXN],num[MAXN];

int s,root,siz[MAXN],d[MAXN];

bool vis[MAXN];

void getroot(int k,int fa)

{

	siz[k] = 1;d[k] = 0;

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

	{

		if(vis[e[i].to] || e[i].to == fa)continue;

		getroot(e[i].to,k);

		siz[k] += siz[e[i].to];

		d[k] = max(d[k],siz[e[i].to]);

	}

	d[k] = max(d[k],s - siz[k]);

	if(d[k] < d[root])root = k;

	return;

}

#define INF 0x3f3f3f3f

int ans = 0;

int dfn[MAXN];

int out[MAXN];

void dfs(int k,int fa)

{

	dfn[++dfn[0]] = k;siz[k] = 1;

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

	{

		if(e[i].to == fa || vis[e[i].to])continue;

		dfs(e[i].to,k);

		siz[k] += siz[e[i].to];

	}

	out[k] = dfn[0];

	return;

}

int f[MAXN][4010];

int cnt[30];

void calc(int k)

{

	dfn[0] = 0;

	dfs(k,0);

	for(int i = 1;i <= dfn[0] + 1;++i)memset(f[i],0,sizeof(f[i]));

	for(int i = dfn[0];i >= 1;--i)

	{

		cnt[0] = 0;int t = num[dfn[i]] - 1;

		for(int j = pri[dfn[i]];j <= m;++j)f[i][j] = f[i + 1][j - pri[dfn[i]]] + val[dfn[i]];

		for(int j = 1;j <= t;t -= j,j <<= 1)cnt[++cnt[0]] = j;

		if(t != 0)cnt[++cnt[0]] = t;

		for(int k = 1;k <= cnt[0];++k)

			for(int j = m;j >= cnt[k] * pri[dfn[i]];--j)

				f[i][j] = max(f[i][j],f[i][j - cnt[k] * pri[dfn[i]]] + cnt[k] * val[dfn[i]]);

		for(int j = 0;j <= m;++j)f[i][j] = max(f[i][j],f[out[dfn[i]] + 1][j]);

	}

	ans = max(ans,f[1][m]);

	return;

}

void divide(int k)

{

	vis[k] = true;

	calc(k);

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

	{

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

		s = siz[e[i].to];root = 0;

		getroot(e[i].to,0);

		divide(root);

	}

	return;

}

void work()

{

	ans = 0;

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

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

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

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

	memset(lin,0,sizeof(lin));

	edgenum = 0;

	memset(vis,false,sizeof(vis));

	int a,b;

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

	{

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

		add(a,b);

	}

	s = n;root = 0;d[0] = INF;

	getroot(1,0);

	divide(root);

	cout << ans << endl;

	return;

} 

int main()

{

	int testcases;

	scanf("%d",&testcases);

	while(testcases--)work();

	return 0;

}