题目

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fir first
#define sec second
const int N = 3005;
int n, m;
int w[N];
int siz[N];
pair<int, int> dp[N][N], h[N];	//fir是根所在块的值, sec是其他块的符合数 
vector<int> g[N];

inline void dfs(int now, int fa){
	dp[now][1] = {w[now], 0};
	siz[now] = 1;
	for(auto i : g[now]){
		if( i == fa )	continue;
		dfs(i, now);
		siz[now] += siz[i];
		for(int j = 1; j <= min(siz[now], m); j++)
			h[j] = {-1e9, 0};
		for(int j = min(siz[now], m); j > 0; j--){
			for(int k = min(siz[i], m); k > 0; k--){
				if( j - k > 0 && j - k <= m ){
					if( h[j].sec < dp[now][j - k].sec + dp[i][k].sec + (dp[i][k].fir > 0) ){
						h[j].sec = dp[now][j - k].sec + dp[i][k].sec + (dp[i][k].fir > 0);
						h[j].fir = dp[now][j - k].fir;
					}
					else if( h[j].sec == dp[now][j - k].sec + dp[i][k].sec + (dp[i][k].fir > 0) )
						h[j].fir = max(h[j].fir, dp[now][j - k].fir);
				}
				if( j - k + 1 > 0 && j - k + 1 <= m ){
					if( h[j].sec < dp[now][j - k + 1].sec + dp[i][k].sec ){
						h[j].sec = dp[now][j - k + 1].sec + dp[i][k].sec;
						h[j].fir = dp[now][j - k + 1].fir + dp[i][k].fir;
					}
					else if( h[j].sec == dp[now][j - k + 1].sec + dp[i][k].sec )
						h[j].fir = max(h[j].fir, dp[now][j - k + 1].fir + dp[i][k].fir);
				}
			}
		}
		for(int j = 1; j <= min(siz[now], m); j++)
			dp[now][j] = h[j];
	}
	return;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	int T;
	cin >> T;
	while( T-- ){
		cin >> n >> m;
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= m; j++)
				dp[i][j] = {-1e9, 0};
		for(int i = 1; i <= n; i++){
			g[i].clear();
			siz[i] = 0;
		}
		for(int i = 1; i <= n; i++)
			cin >> w[i];
		for(int i = 1; i <= n; i++){
			int x;
			cin >> x;
			w[i] = x - w[i];
		}
		for(int i = 1; i < n; i++){
			int x, y;
			cin >> x >> y;
			g[x].push_back(y);
			g[y].push_back(x); 
		}
		dfs(1, 0);
		cout << dp[1][m].sec + (dp[1][m].fir > 0) << "\n";
	}
	return 0;
}