#include <bits/stdc++.h>

#define boAshraf ios_base::sync_with_stdio(false); cin.tie(NULL);
#define ll long long
#define sz(s) (int)(s).size()
#define all(s) (s).begin(),(s).end()
using namespace std;

void File();

void sol();

const int N = 1e6;
int lpf[N + 1];
int freq[N + 1];
int val[(int)2e5+1];
vector<int> prime;

void sieve() {
    for (int i = 2; i <= N; i++) {
        if (lpf[i] == 0) {
            lpf[i] = i;
            prime.push_back(i);
        }
        for (int j: prime) {
            if (j > lpf[i] || 1LL * i * j > N)break;
            lpf[i * j] = j;
        }
    }
}

vector<vector<int>> adj;
vector<vector<int> *> nodes;
vector<int> cnt;
int tot=0,ans=0;
void add(int u) {
    int x=val[u];
    while(x>1){
        int c=lpf[x];
        if(!freq[c]++)tot++;
        while(x%c==0)x/=c;
    }

}

void del(int u) {
    int x=val[u];
    while(x>1){
        int c=lpf[x];
        if(!--freq[c])tot--;
        while(x%c==0)x/=c;
    }
}

void dfsSize(int u = 1, int p = -1) {
    cnt[u] = 1;
    for (int v: adj[u]) {
        if (v == p) continue;
        dfsSize(v, u);
        cnt[u] += cnt[v];
    }
}

void dfs(int u, int p, bool keep = 1) {
    int max_size = 0, bigChild = -1;
    for (int v: adj[u]) {
        if (v == p || cnt[v] <= max_size) continue;
        max_size = cnt[v];
        bigChild = v;
    }
    for (int v: adj[u]) {
        if (v == p || v == bigChild) continue;
        dfs(v, u, 0);
    }
    if (bigChild == -1) {
        nodes[u] = new vector<int>();
    } else {
        dfs(bigChild, u, 1);
        nodes[u] = nodes[bigChild];
    }
    nodes[u]->push_back(u);
    add(u);
    for (int v: adj[u]) {
        if (v == p || v == bigChild) continue;
        for (int ch: *nodes[v]) {
            add(ch);
            nodes[u]->push_back(ch);
        }
    }
    ans+=tot&1;
    if (keep == 0) {
        for (int v: *nodes[u]) {
            del(v);
        }
    }
}

void init(int n, int root = 1) {
    nodes = vector<vector<int> *>(n + 1);
    cnt = vector<int>(n + 1);
    dfsSize(root, -1);
    dfs(1,0);
}


int main() {
    boAshraf
    File();
    int t = 1;
//    cin >> t;
    sieve();
    while (t--) {
        sol();
    }
    return 0;
}

void sol() {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>val[i];
    adj.resize(n+1);
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    init(n);
    cout<<ans;
}

void File() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}