題解區單調隊列優化的題解好像不多（？），怎么都是二進制拆分打爆單調隊列的。來水一發題解。

首先轉化題意，題目即為求一個連通塊使其價格之和不超過 \(m\) 且喜愛度之和最大。如果我們固定一個點為根，要求這個連通塊必須包含這個點，那么就是很樸素的樹上多重背包。

具體的，先跑一邊 dfs 序，然后對于 \(f_{i,j}\) 表示后以 dfs 序第 \(i\) 到第 \(n\) 個點、共花費 \(j\) 元能獲得的最大喜愛度，設其 dfs 序為 \(i\) 的點是 \(u\)。如果 \(u\) 不拿，那么其子樹中的都不能取即 \(f_{i,j}=f_{i+siz_u,j}\)，或者取了 \(u\) 那么 \(f_{i,j}=\max_{1 \leq k \leq d_u} f_{i+1,j-k\times c_i}+k\times w_i\)，直接使用單調隊列維護即可。

如果對每個點為根跑一次樹上背包顯然時間復雜度會爆。而我們發現這個是可以點分治優化的（其實就是有許多相同的連通塊被算了很多次），直接做就完了，時間復雜度為 \(\mathcal{O}(nm \log n)\)。注意轉移的時候 \(u\) 應至少取一次。

const int N=505,M=4005,inf=1e9;
int T,n,m,w[N],c[N],d[N],ans;
vector<int> edge[N];

int rt,sum,siz[N],mxsiz[N];
int tim,dfn[N],lim[N],f[N][M];
bitset<N> vis;
inline void dfs(int u,int fa) {
	siz[u]=1,lim[dfn[u]=++tim]=u;
	for(int v:edge[u]) {
		if(v==fa||vis[v]) continue ;
		dfs(v,u),siz[u]+=siz[v];
	}
	return ;
}
inline void get_root(int u,int fa) {
	mxsiz[u]=0;
	for(int v:edge[u]) {
		if(v==fa||vis[v]) continue ;
		get_root(v,u),mxsiz[u]=max(mxsiz[u],siz[v]);
	}
	mxsiz[u]=max(mxsiz[u],sum-siz[u]);
	if(mxsiz[u]<mxsiz[rt]) rt=u;
	return ;
}
inline int calc(int i,int h,int j,int v) {
	return f[i+1][j*c[v]+h]-w[v]*j;
}
inline void solve(int u) {
	vis[u]=1,tim=0,dfs(u,0);
	for(int i=1;i<=tim+1;i++) for(int j=0;j<=m;j++) f[i][j]=0;
	for(int i=tim;i>=1;i--) {
		for(int j=0;j<=m;j++) f[i][j]=f[i+siz[lim[i]]][j]; // i 子樹都不取
		int v=lim[i];
		for(int h=0;h<c[v];h++) {
			deque<int> dq; // 單調隊列優化多重背包
			for(int j=0;j*c[v]+h<=m;j++) {
				while(!dq.empty()&&dq.front()<j-d[v]) dq.pop_front();
				if(!dq.empty()) f[i][j*c[v]+h]=max(f[i][j*c[v]+h],calc(i,h,dq.front(),v)+w[v]*j);
				while(!dq.empty()&&calc(i,h,dq.back(),v)<=calc(i,h,j,v)) dq.pop_back();
				dq.push_back(j);
			}
		}
	}
	for(int i=0;i<=m;i++) ans=max(ans,f[1][i]);
	for(int v:edge[u]) {
		if(vis[v]) continue ;
		rt=0,sum=siz[v],get_root(v,u),solve(rt);
	}
	return ;
}

int main() {
	read(T),mxsiz[0]=inf;
	while(T--) {
		read(n,m),ans=0;
		for(int i=1;i<=n;i++) read(w[i]);
		for(int i=1;i<=n;i++) read(c[i]);
		for(int i=1;i<=n;i++) read(d[i]);
		for(int i=1;i<=n;i++) edge[i].clear(),vis[i]=0;
		for(int i=1,u,v;i<n;i++) read(u,v),edge[u].pb(v),edge[v].pb(u);
		rt=0,sum=n,get_root(1,0),solve(rt);
		write(ans),_E;
	}
	return 0;
}