#include <iostream>

#define Rep(i, n) for (int i = 1; i <= n; i ++)
#define Rep0(i, n) for (int i = 0; i <= n; i ++)
#define RepG(i, x) for (int i = head[x]; i; i = edge[i].next)
#define v edge[i].to

using namespace std;

const int N = 5010;

struct Edge{ int to, next;} edge[N * 2];
int head[N], num;
void add_edge(int a, int b) { edge[++ num] = (Edge){b, head[a]}, head[a] = num;} 


int prime[110] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 
41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};

int c[N], g[N], id[1 << 25], s[N];

int f[N][25], f0[1510], f1[1510], cnt;

void dfs(int x, int fa)
{
    //cout << x << " " << fa << " " << cnt << endl;
    RepG(i, x) if (v != fa)
        dfs(v, x);
    Rep(i, cnt) f0[i] = f1[i] = 1e9;
    f0[1] = 0;
    RepG(i, x) if (v != fa) {
        Rep(j, cnt) if (f0[j] != 1e9) Rep0(k, 24){
            int tmp = g[j] | (1 << k);
            if (id[tmp]) f1[id[tmp]] = min(f1[id[tmp]], f0[j] + f[v][k]);
            else break;
        }
        Rep(j, cnt) f0[j] = f1[j], f1[j] = 1e9;
    }
    int sx = 0;
    Rep0(i, 24) if (!(c[x] % prime[i])) sx |= 1 << i;
    Rep0(i, 24) f[x][i] = 1e9;
    Rep(i, cnt) if (f0[i] < 1e9) Rep0(j, 24){
        int tmp = g[i] | (1 << j);
        //if (x == 6) cout << g[i] << " " << sx <<  " " << tmp << endl;
        if (id[tmp]) {
            //if (x == 6) cout << "!" << s[id[tmp]] << endl;
            if ((sx & tmp) == tmp){ f[x][j] = min(f[x][j], f0[i]);/* if (x == 6) cout << "!" << endl;*/}
            else f[x][j] = min(f[x][j], f0[i] + s[id[tmp]]);
        }
    }
    //cout << sx << endl; 
    //Rep0(i, 24) cout << x << " " << i << " " << f[x][i] << endl;
}

int main()
{
    int n;
    cin >> n;
    Rep (i, n) cin >> c[i];

    Rep(i, n - 1) {
        int a, b;
        cin >> a >> b;
        add_edge(a, b); add_edge(b, a);
    }
    Rep0(i, (1 << 25) - 1) {
        int sum = 1;
        bool flag = false;
        Rep0(j, 24) if (i & (1 << j)) {
            sum *= prime[j];
            if (sum >= n * 2){ flag = true; break;}
        }
        if (!flag){

            g[++ cnt] = i, s[cnt] = sum, id[i] = cnt;
           // cout << cnt << " " << g[cnt] << " " << sum << endl;
        }
    }

    dfs(1, 0);
    int ans = 1e9;
    Rep0(i, 24) ans = min(ans, f[1][i]);
    cout << ans << endl;

    return 0;
}