#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define ALL(v) v.begin(), v.end()
#define pb push_back
#define SZ(a) ((int)a.size())

const int C = 100;
int arr[5005], sz[5005], prime[10005];
int dp[5005][10005], tmp[10005], n;
//bitset<10005> table[10005];
vector<int> G[5005];

void dfs(int u, int f) {
    sz[u] = 1;
    for (int i : G[u])
        if (i != f) {
            dfs(i, u);
            sz[u] += sz[i];
        }
    int up = 2 * n;
    iota(dp[u] + 2, dp[u] + up + 1, 2);
    dp[u][arr[u]] = 0; 
    for (int i : G[u])
        if (i != f) {
            fill_n(tmp + 1, 2 * n, 2 * n + 1);
            for (int j = 2; j <= up; ++j) {
                if (prime[j]) continue;
                int val = 2 * n + 1;
                for (int k = j; k <= up; k += j)
                    val = min(val, dp[i][k]);
                for (int k = j; k <= up; k += j)
                    tmp[k] = min(tmp[k], val);
            }
            for (int j = 2; j <= up; ++j)
                dp[u][j] += tmp[j], dp[u][j] = min(dp[u][j], 2 * n + 1);
        }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> arr[i];
    for (int i = 2; i <= 10000; ++i)
        if (!prime[i])
            for (int j = i + i; j <= 10000; ++j)
                prime[j] = 1;
    /*for (int i = 2; i <= 10000; ++i)
        for (int j = i; j <= 10000; ++j) {
            int a = i, b = j;
            if (b % a == 0) table[i][j] = table[j][i] = 1;
            else table[i][j] = table[j][i] = table[b % a][a];
        }*/
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        G[u].pb(v);
        G[v].pb(u);
    }
    dfs(1, 1);
    cout << *min_element(dp[1] + 2, dp[1] + 2 * n + 1) << "\n";
}