#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，代表在不同 k 之下，如果不切斷 u，可以省多少成本 // savings[k] = dp[u] - cost_if_kept_connected_with_mod_k vector<long long> dfs(int u, int p) { long long sum_child_dp = 0; // 初始化當前節點的 savings 列表 vector<long long> my_savings; if (n <= 5000) my_savings.assign(n + 1, 0); for (int v : g[u]) { if (v == p) continue; // 遞迴取得子節點的 savings vector<long long> child_savings = dfs(v, u); sum_child_dp += dp[v]; // 如果 N 很大，直接跳過合併邏輯避免 TLE (放棄 Subtask 2, 5) if (n > 5000) continue; // 合併子節點的 savings if (a[v] == a[u] + 1) { // 情況 1: 數值差 1，只要 k > a[v] 都可以連 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]) { my_savings[k] += child_savings[k]; } } } } // 計算 dp[u] dp[u] = INF; if (n <= 5000) { for (int k = a[u] + 1; k <= n; k++) { // Cost = f[k] + sum(dp[child]) - sum(savings[child]) long long cost = f[k] + sum_child_dp - my_savings[k]; if (cost < dp[u]) dp[u] = cost; } } else { // N 很大時的 fallback (雖然過不了但防止 Runtime Error) dp[u] = sum_child_dp + f[min(n, a[u]+1)]; } // 更新 my_savings 以回傳給父節點 // 數學推導: S_u[k] = dp[u] - (sum_child_dp - sum_child_savings) // = dp[u] - sum_child_dp + current_accumulated_savings if (n <= 5000) { long long base_diff = dp[u] - sum_child_dp; for (int k = 1; k <= n; k++) { if (k > a[u]) { my_savings[k] += base_diff; } else { my_savings[k] = 0; // k 不合法，無法連接，saving 為 0 } } } 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); } dfs(1, 0); cout << dp[1] << endl; }