1
#include<bits/stdc++.h>
2
using namespace std;
3
#define ll  long long
4
#define all(d) d.begin(),d.end()
5
#define test int t;cin>>t;while(t--)
6
#define ones(n) __builtin_popcount(n)
7
#define last(n) ____builtin_clz(len)
8
const int dx8[8] = {1, 0, -1, 0,-1,-1,1,1};
9
const int dy8[8] = {0, 1, 0, -1, -1, 1, -1, 1};
10
int dx[] = {+0, +0, +1, -1};
11
int dy[] = {+1, -1, +0, +0};
12
char di[]={'R','L','D','U'};
13
void JOO() {
14
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
15
#ifndef ONLINE_JUDGE
16
    freopen("input.txt", "r", stdin);
17
    freopen("output.txt", "w", stdout);
18
#endif
19
}
20
const int N=2e5+5,M=1e3+5,LOG=20,inf=0x3f3f3f3f;
21
int MOD=1e9+7;
22
ll infLL=0x3f3f3f3f3f3f3f3f;
23
bool prime[N+1];
24
vector<ll> primes;
25
void sieve(){
26
    // O(n log log n)
27
    memset(prime, true, sizeof(prime));
28
    prime[2] = true;
29
    for(int p = 2; p <= N; p++){
30
        if(prime[p]){
31
            primes.push_back(p);
32
            for (int i = p * 2; i <= N; i += p){
33
                prime[i] = false;
34
            }
35
        }
36
    }
37
}
38
map<int,int>freq;
39
vector<ll> factorize(ll x){
40
    vector<ll>ret;
41
    for(auto p : primes){
42
        if(p * p > x)
43
            break;
44
        if(x%p==0)
45
 
46
        while(x%p == 0){
47
            x/=p;
48
            freq[p]++;
49
        }
50
    }
51
    if(x != 1)
52
    {
53
        freq[x]++;
54
    }
55
    return ret;
56
}
57
int MX=(1<<9)-1;
58
int dp[M][(1<<9)+5];
59
vector<int>adj[M];
60
int val[M];
61
void dfs(int u,int p)
62
{
63
    dp[u][val[u]]=1;
64
    dp[u][0]=1;
65
    for(int v:adj[u])
66
    {
67
        if(v==p)
68
            continue;
69
        dfs(v,u);
70
        for (int i = 0; i <= MX; ++i) {
71
            for (int j = 0; j <= MX; ++j) {
72
                dp[u][i|j]=min(dp[u][i|j],dp[u][i]+dp[v][j]);
73
            }
74
        }
75
    }
76
}
77
void solve()
78
{
79
    int n;cin>>n;
80
    int lc=1;
81
    for (int i = 0; i < n; ++i) {
82
        cin>>val[i];
83
        lc=lcm(lc,val[i]);
84
    }
85
    factorize(lc);
86
    vector<int>factors;
87
    int mx=0,cnt=0;
88
    for(auto[x,y]:freq)
89
    {
90
        factors.push_back(pow(x,y));
91
        mx|=(1<<cnt);
92
        cnt++;
93
    }
94
    for (int i = 0; i < n; ++i) {
95
        int msk=0;
96
        for (int j = 0; j < factors.size(); ++j) {
97
            if(factors[j]<=val[i] && val[i]%factors[j]==0)
98
            {
99
                msk|=(1<<j);
100
            }
101
        }
102
        val[i]=msk;
103
    }
104
    for (int i = 0; i < n-1; ++i) {
105
        int u,v;cin>>u>>v;
106
        u--,v--;
107
        adj[u].push_back(v);
108
        adj[v].push_back(u);
109
    }
110
    memset(dp,inf,sizeof dp);
111
    dfs(0,-1);
112
    int ans=inf;
113
    for (int i = 0; i < n; ++i) {
114
        ans=min(ans,dp[i][mx]);
115
    }
116
    cout<<ans<<'\n';
117
 
118
}
119
signed main() {
120
    JOO();
121
    sieve();
122
//    int cnt=1;
123
//    test
124
    {
125
//        cout << "Case " << "#" << cnt++ << ": ";
126
        solve();
127
    }
128
}