參考題解：
嚴格鴿
Mercury_City

思路：

根據 \(ti \le 3\) 這個數據范圍，我們可以知道蝴蝶最晚消失的時間至少是3秒。
對于一個根節點 \(u\) ,假設其兒子 \(v_1, v_2\) ,我們到達 \(u\) 點之后就會驚動 \(v\) 處的蝴蝶。

當所有兒子的 \(ti < 3\) 時， 我們就在所有兒子中選擇一個蝴蝶最多的兒子 \(v_1\) 一路走到底。又因為時間很多，完全可以把所有點走完，所以直接統計就可以了。

當所有兒子的 \(ti = 3\) 時，假設這個節點是 \(v_2\) 。那么我們可以先走 \(v_1\) 拿蝴蝶，之后再回到 \(u\) ，再去 \(v_2\)。這時候就可以分類討論：

1. \(v_2\) 上的蝴蝶是最大的：

此時就在其他子節點中找到一個最大的先走，然后再走 \(v_2\)

2. \(v_2\) 上的蝴蝶不是最大的：

這時也是在其他節點找一個最大的先走，再走 \(v_2\)

由此，我們可設計狀態為 \(f[u]\) 表示：不選 \(u\) 點處蝴蝶（\(u\) 點處蝴蝶飛走了），選從 \(u\) 點出發的所有子節點所得的最大值。

定義 \(sum[u]\) 表示，\(u\) 點的子節點 \(f[v]\) 的和。
畫了個圖幫助理解：

狀態轉移：

根據上面的分析，我們可得狀態轉移：

1. \(u\) 的子節點中，\(ti = 3\) 不存在的情況：

   無論我們選哪個子節點，最終的結果都是：\(f[u] = max(f[u]，sum[u] + a[v])\)

2. \(u\) 的子節點中，\(ti = 3\) 存在的情況：

   首先我們先到了點 \(v_1\) ，答案要加上\(a[v_1]\)，拿完之后我們跑去 \(v_2\) 了，此時再加上 \(v_2\) 處的蝴蝶 \(a[v_2]\)。因為我們不往 \(v_1\) 下面走了，而此時 \(v_1\) 的子節點也被驚動了，肯定會飛走，可以表示為表示為 \(sum[u] - f[v_1]\) 。又因為時間無限多，我們以后可能還會往 \(v_1\) 的 子節點 的 子節點 走，所以要再加上 \(sum[v_1]\) 。最終的方程就是：\(f[u] = max(f[u], sum[u] - f[v_1] + a[v_1]+a[v_2] + sum[v_1])\)

代碼：

#include<bits/stdc++.h>

#define int long long
using namespace std;
#define fi first
#define se second
#define cf int T;cin >> T;while (T --)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

typedef pair<int, int> pii;
const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f;
int dp[N];
int sum[N], t[N];
int a[N];
vector<int> g[N];
int n, u, v;

void dfs(int u, int fa) {
	int mx = 0;
	for (auto v: g[u]) {
		if (v == fa) continue;
		dfs(v, u);
		sum[u] += dp[v];
		mx = max(mx, a[v]);
	}
	dp[u] = sum[u] + mx;
	
	mx = 0;
	int idx = 0;
	for (auto v: g[u]) {
		if (v == fa) continue;
		if (t[v] == 3 && a[v] > mx)
			mx = a[v], idx = v;
	}
	int minn = - inf * inf;
	for (auto v: g[u]) {
		if (v == fa) continue;
		if (v != idx)
			minn = max(minn, sum[v] + a[v] - dp[v]);
	}
	dp[u] = max(dp[u], sum[u] + mx + minn);
	
	mx = 0, idx = 0;
	minn = - inf * inf;
	for (auto v: g[u]) {
		if (v == fa) continue;
		if (sum[v] + a[v] - dp[v] > minn)
			minn = sum[v] + a[v] - dp[v], idx = v;
	}
	
	for (auto v: g[u]) {
		if (v == fa) continue;
		if (v != idx && t[v] == 3)
			mx = max(mx, a[v]);
	}
	dp[u] = max(dp[u], sum[u] + mx + minn);
}

void solve() {
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		g[i].clear();
		dp[i] = sum[i] = 0;
	}
	for (int i = 1; i <= n; i ++) cin >> a[i];
	for (int i = 1; i <= n; i ++) cin >> t[i];
	for (int i = 1; i <= n - 1; i ++) {
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1, 0);
	cout << dp[1] + a[1] << endl;
}

signed main() {
#ifndef ONLINE_JUDGE
	freopen("cin.in", "r", stdin);
	freopen("cout.out", "w", stdout);
#endif
	IOS
	cf solve();
	return 0;
}