#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 5e3 + 2;
const int MOD = 1e9 + 7 ;


int a[N] ;

vector<int> ad[N];

int dp[N][N*2] , n;

vector<int> pr[2*N + 4] ;

bool fr[N+N+4] ;


int sol( int  i , int x , int p = 0)
{
    int & ret= dp[i][x] ;

    if(~ret)return ret ;

    bool s = 1 ;

    for(int ch : pr[a[i]]) fr[ch] =1 ;

    for(int pri : pr[x])  s&= fr[pri] ;

    for(int ch : pr[a[i]]) fr[ch] = 0 ;

    if(s) x= a[i] , ret =0 ;
    else ret = x ;

    int sz = (int) pr[x].size() ;

    for(int ch : ad[i])
    {
        if(ch == p) continue;

        int mn = 2*n;

        for(int msk = 1 ; msk < 1 << sz; msk++)
        {
            int y = 1 ;

            for(int j = 0 ;j < sz ; j++) {

                if( msk & (1 << j) ) y *= pr[x][j] ;
            }

            mn = min(mn , sol(ch , y , i) ) ;
        }

        ret += mn ;
    }

    ret = min(ret , 2*n) ;

    return ret ;
}


int main()
{
    cin.tie(0);cin.sync_with_stdio(0);
    cout.tie(0);cout.sync_with_stdio(0);

    for(int i =2 ; i <= 100; i++)
    {
        if(pr[i].empty() )
        {
            for(int j = i ; j <= N+N ; j += i) pr[j].push_back(i);
        }
    }

    cin >> n ;

    for(int i =1 ; i <= n ;i++) cin >> a[i] ;


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

    memset(dp , -1 , sizeof dp) ;

    int ans = 2*n ;

    for(int v = 2 ; v <= N+N ; v++) ans = min(ans , sol(1 , v) ) ;

    cout << ans ;

    return 0;
}