重学0/1背包
先是写成了完全背包
后来又写了个if(lim<=0)return; 父亲在lim=0时得不到信息了
#include<bits/stdc++.h>
using namespace std;
#define fp(i,l,r) for(register int (i)=(l);i<=(r);++(i))
#define fd(i,l,r) for(register int (i)=(l);i>=(r);--(i))
#define fe(i,u) for(register int (i)=front[(u)];(i);(i)=e[(i)].next)
#define mem(a) memset((a),0,sizeof (a))
#define O(x) cerr<<#x<<':'<<x<<endl
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
void wr(int x){
if(x<0)x=-x,putchar('-');
if(x>=10)wr(x/10);
putchar('0'+x%10);
}
const int MAXN=505,MAXM=4010,mod=998244353;
struct tEdge{
int v,next;
}e[MAXN<<1];
int front[MAXN],tcnt,sze[MAXN],rt,rtx,S,n,m;
bool used[MAXN];
inline void adde(int u,int v){
e[++tcnt]=(tEdge){v,front[u]};front[u]=tcnt;
}
void getrt(int u,int f){
sze[u]=1;int t=0;
fe(i,u){
int v=e[i].v;if(used[v]||v==f)continue;
getrt(v,u);sze[u]+=sze[v];t=max(t,sze[v]);
}
t=max(t,S-sze[u]);
if(t<rtx)rtx=t,rt=u;
}
int w[MAXN],c[MAXN],d[MAXN],dp[MAXN][MAXM],ans;//这里dp[u][j]表示除了强制选的 剩下自由的体积为j
void dfs(int u,int f,int lim){
if(lim<0)return;
fp(i,0,lim)dp[u][i]=dp[f][i]+w[u];int t=d[u];
for(int i=1;i<t;t-=i,i<<=1){
int p=c[u]*i,v=w[u]*i;
fd(j,lim,p)dp[u][j]=max(dp[u][j],dp[u][j-p]+v);
}
int p=c[u]*t,v=w[u]*t;
fd(j,lim,p)dp[u][j]=max(dp[u][j],dp[u][j-p]+v);
fe(i,u){
int v=e[i].v;if(used[v]||v==f)continue;
dfs(v,u,lim-c[v]);
fp(j,0,lim-c[v])dp[u][j+c[v]]=max(dp[u][j+c[v]],dp[v][j]);
}
}
void dfs(int u){
used[u]=1;
dfs(u,0,m-c[u]);
fp(i,0,m-c[u])ans=max(ans,dp[u][i]);
fe(i,u){
int v=e[i].v;if(used[v])continue;
S=sze[v];rtx=1e9;getrt(v,u);dfs(rt);
}
}
inline void solve(){
ans=-1e9;tcnt=0;mem(front);mem(used);
n=read();m=read();
fp(i,1,n)w[i]=read();fp(i,1,n)c[i]=read();
fp(i,1,n)d[i]=read()-1;
fp(i,1,n-1){
int u=read(),v=read();adde(u,v);adde(v,u);
}
rtx=1e9;S=n;getrt(1,0);dfs(rt);
printf("%d
",ans);
}
main(){
int tt=read();
while(tt--)solve();
return 0;
}