#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long long lint;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

const int MAXM = 1e6+10;
bool prime[MAXM];
int val[MAXM+10];
vector<int> P;
void sieve()
{
    fill(prime, prime+MAXM, true);
    prime[0]=prime[1]=1;
    for(int n=2; n<MAXM; n++)
    {
        if(prime[n])
        {
            P.push_back(n);
            val[n]=n;
        }
        for(int pr : P)
        {
            ll x=(ll)n*pr;
            if(x>=MAXM) break;
            prime[x]=false;
            val[x]=n;

            if(n%pr==0) break;
        }
    }
}

int N, A[MAXN+10];
vector<int> adj[MAXN+10];

int par[MAXN+10], dep[MAXN+10];

void dfs(int now, int bef, int d)
{
    par[now]=bef;
    dep[now]=d;
    for(int nxt : adj[now])
    {
        if(nxt==bef) continue;
        dfs(nxt, now, d+1);
    }
}

vector<int> V[MAXM+10];
bool chk[MAXN+10];

int ans=0;

struct UF
{
    int par[MAXN+10], sz[MAXN+10];
    void init() { for(int i=1; i<=N; i++) par[i]=i, sz[i]=1; }
    int Find(int x)
    {
        if(x==par[x]) return x;
        return par[x]=Find(par[x]);
    }
    void Union(int x, int y)
    {
        x=Find(x); y=Find(y);
        par[x]=y;
        sz[y]+=sz[x];
        ans=max(ans, sz[y]);
    }
    void flush(int x) { par[x]=x; sz[x]=1; }
}uf;

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    
    sieve();

    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i];
    for(int i=1; i<N; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 0, 1);

    for(int i=1; i<=N; i++)
    {
        int x=A[i];
        while(x>1)
        {
            V[val[x]].push_back(i);
            x/=val[x];
        }
    }

    uf.init();
    for(int i=2; i<MAXM; i++)
    {
        sort(V[i].begin(), V[i].end());
        V[i].erase(unique(V[i].begin(), V[i].end()), V[i].end());

        vector<pii> VV;
        for(auto it : V[i]) VV.push_back({dep[it], it});
        sort(VV.begin(), VV.end());

        for(auto [_, it] : VV)
        {
            ans=max(ans, 1);
            chk[it]=true;
            if(chk[par[it]]) uf.Union(it, par[it]);
        }
        
        for(auto it : V[i]) uf.flush(it), chk[it]=false;
    }

    cout << ans << '\n';
}