#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

#define el '\n'
#define FIO ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef complex<ld> pt;
typedef unsigned long long ull;

template<typename T, typename X>
using hashTable = gp_hash_table<T, X>;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

// mt19937_64 for long long
mt19937 rng(std::chrono::system_clock::now().time_since_epoch().count());

const int N = 5e3 + 5;

vector<int> G[N];
int dp[N][1005], curVal[N], g[1005][1005];

int solve(int node, int par, int val) {
    int &ret = dp[node][val];
    if (~ret)
        return ret;

    ret = 0;
    for (auto &ch: G[node]) {
        if (ch == par)
            continue;

        int mn = 1e9;
        for (int newVal = 2; newVal <= 1000; newVal++) {
            if (g[val][newVal] == 1)
                continue;
            mn = min(mn, solve(ch, node, newVal) + (curVal[ch] == newVal ? 0 : newVal));
        }
        ret = min(ret + mn, (int) 1e9);
    }
    return ret;
}

void doWork() {
    int n;
    cin >> n;
    memset(dp, -1, sizeof dp);
    for (int i = 1; i <= n; i++)
        cin >> curVal[i];

    for (int i = 1; i <= 1000; i++)
        for (int j = 1; j <= 1000; j++)
            g[i][j] = __gcd(i, j);


    for (int i = 0, u, v; i < n - 1; i++)
        cin >> u >> v, G[u].push_back(v), G[v].push_back(u);

    int ans = 1e9;
    for (int i = 2; i <= 1000; i++)
        ans = min(ans, solve(1, -1, i) + (curVal[1] == i ? 0 : i));
    cout << ans;
}

signed main() {
    FIO
    int T = 1;
//    cin >> T;
    for (int i = 1; i <= T; i++)
        doWork();
}