// Hey there.. I love Eddard <3
 
//#pragma GCC optimize ("Ofast, no-stack-protector, unroll-loops, fast-math, O3")
 
#include <bits/stdc++.h>
 
using namespace std;
 
void fileIO () {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
}
 
void fastIO () {
    std::ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
}
 
int main_ ();
 
int main () {
    fastIO ();
    //fileIO ();
    int t = 1;
    //cin >> t;
    while(t--) {
        main_ ();
    }
    return 0;
}
 
const int N = 5e3 + 5;

vector<int> f[N*2];

int MAX;

int n, val[N];
int u, v;
vector<int> adj[N];

bool gcd(int a, int b){
    if((a&1)==0 && (b&1)==0){
        return 1;
    }
    int i = 0, j = 0;
    while(i < f[a].size() && j < f[b].size()){
        if(f[a][i] < f[b][j]){
            ++i;
        }
        else if(f[a][i] > f[b][j]){
            ++j;
        }
        else{
            return 1;
        }
    }
    return 0;
}
int dfs(int node, int par, int g){
    int ans = MAX;
    if(gcd(g, val[node])){
        int cur = 0;
        for(int ch:adj[node]){
            if(ch!=par){
                cur += dfs(ch,node,val[node]);
            }
        }
        ans = min(ans, cur);
    }
    
    for(int i=2;i<ans;++i){
        if(!gcd(g,i)){
            continue;
        }
        if(i == val[node]){
            continue;
        }
        int cur = i;
        for(int ch:adj[node]){
            if(ch!=par){
                cur += dfs(ch,node,i);
            }
        }
        ans = min(ans, cur);
    }
    return ans;
}

vector<int> factorize(int x){
    vector<int> factors ;
    while(x%2 == 0){
        x /= 2;
    }
    for(int i = 3; i * i <= x; i += 2){
        if(x%i==0){
            factors.push_back(i);
            while(x%i==0){
                x /= i;
            }
        }
    }
    if(x>2){
        factors.push_back(x);
    }
    return factors ;
}

int main_ () {
    cin >> n;
    MAX = n * 2;
    for(int i=3;i<=MAX;++i){
        f[i] = factorize(i);
    }
    for(int i=1;i<=n;++i){
        cin >> val[i];
    }
    for(int i=1;i<n;++i){
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    cout << dfs(1,1,0) << endl;
    return 0;
}