#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll inf=1e18,siz=200;
ll n,m,i,j,k,l,r,x,y,z,w,s,t,a[1100000],dp[5500][220],adj[220][220];
vector<ll> v[1100000];
void f(ll x,ll y)
{
    ll i;
    for(auto xx:v[x])
    {
        if(xx==y)
            continue;
        f(xx,x);
    }
    for(i=1;i<=siz;i++)
    {
        if(i!=a[x])
        dp[x][i]=i;
        else
        dp[x][i]=0;
    }
    ll s;
    for(i=1;i<=siz;i++)
    {
        for(auto xx:v[x])
        {
            if(xx==y)
            continue;
            s=inf;
            for(j=1;j<=siz;j++)
            {
                if(adj[i][j])
                s=min(s,dp[xx][j]);
            }
            dp[x][i]+=s;
        }

    }
    return;
}
ll gcd(ll x,ll y)
{
    if(x>y)
    swap(x,y);
    if(x==0)
        return y;
    return gcd(y%x,x);
}
int main()
{
    for(i=1;i<=siz;i++)
        for(j=1;j<=siz;j++)
    {
        if(gcd(i,j)>=2)
            adj[i][j]=1;
    }
    scanf("%lld",&n);
    for(i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    for(i=1;i<n;i++)
    {
        scanf("%lld %lld",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=200;j++)
        {
            dp[i][j]=inf;
        }
    }
    f(1,0);
    s=inf;
    for(i=1;i<=200;i++)
    {
        //printf("(%lld)\n",dp[1][i]);
        s=min(s,dp[1][i]);
    }
    printf("%lld",s);
}