#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] ;

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

         if(~ret)return ret ;

         bool s = 1 ;
         for(int pri : pr[x])  s &= (bool)( count( pr[a[i]].begin() , pr[a[i]].end() , pri) ) ;

         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 <= N+N ; 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;
}