#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5, M = 1e6 + 5;
int a[N];
bitset<N> is_same_group;
vector<int> prime, point, prime_div[M], prime_node[M], graph[N];
int dsu[N];
int Find(int x){
    if(dsu[x] < 0)
        return x;
    return dsu[x] = Find(dsu[x]);
}
int Union(int x, int y){
    x = Find(x);
    y = Find(y);
    if(x == y)
        return -dsu[x];
    if(dsu[x] > dsu[y])
        swap(x, y);
    dsu[x] += dsu[y];
    dsu[y] = x;
    return -dsu[x];
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        dsu[i] = -1;
    }
    int x, y;
    for(int i = 0; i < n - 1; i++){
        cin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    for(int i = 2; i <= 1e6; i++){
        if(prime_div[i].empty()){
            prime.push_back(i);
            prime_div[i].push_back(i);
            for(int j = i * i; j <= 1e6; j += i){
                prime_div[j].push_back(i);
            }
        }
    }
    for(int i = 1; i <= n; i++){
        for(auto j : prime_div[a[i]]){
            prime_node[j].push_back(i);
        }
    }
    int ans = 0;
    for(auto i : prime){
        for(auto j : prime_node[i]){
            is_same_group[j] = 1;
        }
        int maxc = !prime_node[i].empty();
        for(auto j : prime_node[i]){
            for(auto u : graph[j]){
                if(is_same_group[u]){
                    maxc = max(maxc, Union(j, u));
                }
            }
        }
        ans = max(ans, maxc);
        for(auto j : prime_node[i]){
            is_same_group[j] = 0;
            dsu[j] = -1;
        }
    }
    cout << ans << '\n';
}