#include <bits/stdc++.h> using namespace std; const int mxn = 3e5+10; const long long INF = 1e18; int n; int a[mxn]; int f[mxn]; vector<int> g[mxn]; long long dp[mxn]; // 預處理因數，只用於 N <= 5000 的情況 vector<int> divs_list[5005]; void init_divs() { if (n > 5000) return; for (int i = 1; i <= n; i++) { for (int j = i; j <= n; j += i) { divs_list[j].push_back(i); } } } // DFS 回傳 vector vector<long long> dfs(int u, int p) { long long sum_child_dp = 0; // 初始化：找出最大的子節點 vector 來繼承 (啟發式合併的一點點影子，減少複製) // 對於 N=5000 這不是必須的，但能讓執行更穩 vector<long long> my_savings; if (n <= 5000) my_savings.assign(n + 1, 0); for (int v : g[u]) { if (v == p) continue; vector<long long> child_savings = dfs(v, u); sum_child_dp += dp[v]; if (n > 5000) continue; // 大測資直接跳過 // 合併子節點的 savings if (a[v] == a[u] + 1) { // 情況 1: 數值差 1 (最常見，跑滿 O(N)) for (int k = a[v] + 1; k <= n; k++) { my_savings[k] += child_savings[k]; } } else if (a[v] <= a[u]) { // 情況 2: 數值變小或不變 (只跑因數，很快) int diff = a[u] + 1 - a[v]; for (int k : divs_list[diff]) { if (k > a[v]) { // 確保 k 合法 my_savings[k] += child_savings[k]; } } } } // --- 計算 dp[u] --- dp[u] = INF; if (n <= 5000) { // 嘗試所有合法的 k for (int k = a[u] + 1; k <= n; k++) { // Cost = f[k] + (所有子樹切斷的總成本) - (連接省下的錢) long long cost = f[k] + sum_child_dp - my_savings[k]; if (cost < dp[u]) dp[u] = cost; } } else { // N > 5000 的保底邏輯 (隨便算一個合法的，防止崩潰) dp[u] = sum_child_dp + f[min(n, a[u]+1)]; } // --- 準備回傳給父節點 --- // 我們要更新 my_savings，讓它代表「如果不切斷 u，父節點能省多少」 // 公式: New_Savings[k] = max(0, dp[u] - (Cost_if_connected)) // Cost_if_connected = sum_child_dp - old_savings[k] // 所以 New_Savings[k] = max(0, dp[u] - sum_child_dp + old_savings[k]) if (n <= 5000) { long long base_diff = dp[u] - sum_child_dp; for (int k = 1; k <= n; k++) { if (k > a[u]) { // 這是最關鍵的修正：加上 max(0LL, ...) // 如果連線比切斷還貴，那就選擇切斷 (saving = 0)，不要倒扣！ my_savings[k] = max(0LL, my_savings[k] + base_diff); } else { my_savings[k] = 0; // k 不夠大，無法連接 } } } return my_savings; } int main(){ ios::sync_with_stdio(0); cin.tie(0); if (!(cin >> n)) return 0; init_divs(); for(int i = 1 ; i <= n ; i++) cin >> a[i]; for(int i = 1 ; i <= n ; i++) cin >> f[i]; for(int i = 0 ; i < n - 1 ; i++){ int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } // 題目: 節點 1 為根 dfs(1, 0); cout << dp[1] << endl; }