Untitled

#include<iostream>
#include <bits/stdc++.h>

#define ll long long
#define ull unsigned long long
#define ld long double
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 1e3 + 6, mod = 1e9 + 7;

int a[N];
int val[N];
vector<int> adj[N];

vector<int> factorize(int n) {
    vector<int> v;
    for (int i = 2; i * i <= n; i++) {
        if (n % i)continue;
        v.push_back(1);
        while (n % i == 0) {
            n /= i;
            v.back() *= i;
        }
    }
    if (n > 1)v.push_back(n);
    return v;
}

int nxt[N], first_child[N];

int dfs(int node, int p) {

    int last = 0;
    for (auto child: adj[node]) {
        if (child == p)continue;
        if (first_child[node] == 0)first_child[node] = child;
        nxt[last] = child;
        last = child;
        dfs(child, node);
    }
}

int dp[N][N];

int solve(int node, int mask) {
    if (mask == 0) return 0;
    if (node == 0)return 1e9;

    int &ans = dp[node][mask];
    if (ans != -1)return ans;

    ans = solve(nxt[node], mask);
    mask -= mask & val[node];

    for (int submask = mask; ; submask = (submask - 1) & mask) {
        ans = min(ans, 1 + solve(first_child[node], submask) + solve(nxt[node], mask ^ submask));
        if(submask == 0)break;
    }
    return ans;
}

void doWork() {
    int n;
    cin >> n;
    int lcm = 1;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        lcm = 1ll * lcm / gcd(lcm, a[i]) * 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);
    }

    auto v = factorize(lcm);
    int mask = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < v.size(); j++) {
            if (a[i] % v[j] == 0) {
                val[i] |= 1 << j;
            }
        }
        mask |= val[i];
    }
    memset(dp, -1, sizeof dp);

    int ans = n;
    dfs(1, 0);

    for (int i = 1; i <= n; i++) {
        ans = min(ans, 1 + solve(first_child[i], mask ^ val[i]));
    }
    cout << ans;
}

int main() {
    IO
    int t = 1;

//    cin >> t;

    for (int i = 1; i <= t; i++) {
        //  cout << "Case #" << i << ": ";
        doWork();
    }
}