文件详细信息

下载本文件

本文件的大小为 2287 字节。

#include<cstdio>
#include<cstring>
namespace IO{
	const int ARR_SIZE=1<<20;
	#define gc() ((IO::si!=IO::ti||(IO::ti=(IO::si=IO::input)+fread(IO::input,1,IO::ARR_SIZE,stdin))),IO::si!=IO::ti?*(IO::si++):EOF)
	#define pc(ch) ((IO::o.so!=IO::o.to||(fwrite(IO::o.output,1,IO::ARR_SIZE,stdout),IO::o.so=IO::o.output)),*(IO::o.so++)=ch)
	char input[ARR_SIZE],*si=input,*ti=input;
	struct Output_Stream{
		char output[ARR_SIZE],*so=output,*to=output+ARR_SIZE;
		~Output_Stream(){
			if(so==output)return;
			fwrite(output,1,so-output,stdout);
			so=output;
		}
	}o;
	template<typename T>
	void read(T&num){
		int ch=gc();
		num=0;
		while(ch<48||ch>57)ch=gc();
		while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=gc();
	}
	template<typename T>
	void write(T a){
		static int ch[50],cnt=0;
		if(a<0)pc('-'),a=-a;
		if(a==0)pc('0');
		while(a)ch[++cnt]=a%10|48,a/=10;
		while(cnt)pc(ch[cnt--]);
	}
}
using IO::read;
using IO::write;
typedef long long ll;
const int maxn=3000;
int n,m,a[maxn+1];
int head[maxn+1],total;
struct Edge{
	int to,next;
}e[(maxn-1)*2+1];
void add(const int u,const int v){
	e[++total]=Edge{v,head[u]};
	head[u]=total;
}
int size[maxn+1];
int f[maxn+1][maxn+1],tmpf[maxn+1];
ll g[maxn+1][maxn+1],tmpg[maxn+1];
void dfs(const int u,const int from){
	size[u]=1;
	f[u][1]=0;
	g[u][1]=a[u];
	int _f;
	ll _g;
	for(int i=head[u];i;i=e[i].next){
		const int v=e[i].to;
		if(v==from)continue;
		dfs(v,u);
		memset(tmpf+1,0,sizeof(int)*(size[u]+size[v]));
		memset(tmpg+1,63,sizeof(ll)*(size[u]+size[v]));
		for(int i=1;i<=size[u];i++)
			for(int j=1;j<=size[v];j++){
				_f=f[u][i]+f[v][j]+(g[v][j]<0),_g=g[u][i];
				if(tmpf[i+j]<_f||(tmpf[i+j]==_f&&tmpg[i+j]>_g))tmpf[i+j]=_f,tmpg[i+j]=_g;
				_f=f[u][i]+f[v][j],_g=g[u][i]+g[v][j];
				if(tmpf[i+j-1]<_f||(tmpf[i+j-1]==_f&&tmpg[i+j-1]>_g))tmpf[i+j-1]=_f,tmpg[i+j-1]=_g;
			}
		size[u]+=size[v];
		memcpy(f[u]+1,tmpf+1,sizeof(int)*size[u]);
		memcpy(g[u]+1,tmpg+1,sizeof(ll)*size[u]);
	}
}
void solve(){
	read(n),read(m);
	for(int i=1;i<=n;i++)read(a[i]);
	for(int i=1,v;i<=n;i++)read(v),a[i]-=v;
	memset(head+1,0,sizeof(int)*n);
	total=0;
	for(int i=1,u,v;i<n;i++){
		read(u),read(v);
		add(u,v),add(v,u);
	}
	dfs(1,0);
	write(f[1][m]+(g[1][m]<0)),pc('\n');
}
int main(){
	int t;
	read(t);
	while(t--)solve();
	return 0;
}