#include <bits/stdc++.h> #define ll long long using namespace std; int N; int A[300001], F[300001], MIN[300001]; vector <int> VG[300001]; int pos, ET[300001]; void ETDFS(int node, int parent = 0) { ET[++pos] = node; for(int x : VG[node]) if(x != parent) ETDFS(x, node); return; } ll DPC[300002]; void Chain() { for(int i = 1; i <= N; i++) if(VG[i].size() > 2) return; if(VG[1].size() > 1) return; ETDFS(1); for(int i = N; i; i--) { DPC[ET[i]] = MIN[A[ET[i]] + 1] + DPC[ET[i + 1]]; int k = A[ET[i]] + 1; bool flag = false; for(int j = i + 1; j <= N; j++) { if(A[ET[j]] == (A[ET[j - 1]] + 1)) { if(flag && (A[ET[j]] >= k)) break; k = max(k, A[ET[j]] + 1); } else if(!A[ET[j]]) { if(flag && (k != (A[ET[j - 1]] + 1))) break; if(k > (A[ET[j - 1]] + 1)) break; k = A[ET[j - 1]] + 1; flag = true; } else break; if(flag) DPC[ET[i]] = min(F[k] + DPC[ET[j + 1]], DPC[ET[i]]); else DPC[ET[i]] = min(MIN[k] + DPC[ET[j + 1]], DPC[ET[i]]); } } cout << DPC[1] << '\n'; exit(0); } ll DP[5001][5001]; void DPDFS(int node, int parent = 0) { if(VG[node].size() == 1) {DP[0][node] = MIN[A[node] + 1]; return;} DP[0][node] = MIN[A[node] + 1]; for(int x : VG[node]) { if(x == parent) continue; DPDFS(x, node); DP[0][node] += DP[0][x]; for(int k = A[node] + 1; k <= N; k++) { if(((A[node] + 1) % k) != A[x]) DP[k][node] += DP[0][x]; else DP[k][node] += DP[k][x]; } } for(int k = A[node] + 1; k <= N; k++) DP[0][node] = min(DP[k][node] + F[k], DP[0][node]); return; } void Brute() { if(N > 5000) return; DPDFS(1); cout << DP[0][1] << '\n'; exit(0); } int main() { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> N; for(int i = 1; i <= N; i++) cin >> A[i]; for(int i = 1; i <= N; i++) cin >> F[i]; MIN[N] = F[N]; for(int i = N - 1; i; i--) MIN[i] = min(MIN[i + 1], F[i]); int u, v; for(int i = 1; i < N; i++) { cin >> u >> v; VG[u].push_back(v); VG[v].push_back(u); } Chain(); Brute(); return 0; }