#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<vector>
#include<numeric>
#include<cmath>
using namespace std;
#define ll long long
#define ge getchar 
#define pun putchar('\n')
#define pu putchar
#define puk putchar(' ')
#define pb push_back
typedef vector<int> vint;
const int nn=5006,mm=nn*2;
int n,a[nn];
int z[nn],x[mm],t[mm],f[nn][101];
void ff(int u,int fu){
	for(int k=2;k<=100;k++)f[u][k]=(u==k)?0:k;
	for(int i=z[u];i;i=x[i]){
		int v=t[i];
		if(v!=fu){
			ff(v,u);
			for(int k=2;k<=100;k++){
				int zx=f[v][k];
				for(int h=2;h<=100;h++)if(__gcd(k,h)>1){
					zx=min(zx,f[v][h]);
				}
				f[u][k]+=zx;
			}
		}
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	int ki=1;
	for(int i=2;i<=n;i++){
		int u,v;scanf("%d%d",&u,&v);
		x[++ki]=z[u],z[u]=ki,t[ki]=v;
		x[++ki]=z[v],z[v]=ki,t[ki]=u;
	}
	ff(1,0);
	int zx=f[1][2];
	for(int k=2;k<=100;k++)zx=min(zx,f[1][k]);
	cout<<zx<<endl;
	return 0;
}