// Hey there.. I love you <3

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/numeric>

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ld = long double;
using L = __int128;

#define fast cin.tie(0), cin.sync_with_stdio(0)
FILE *stream;

#define input(x) freopen_s(&stream, (x), "r", stdin)
#define output(x) freopen_s(&stream, (x), "w", stdout)
#define all(x) x.begin(), x.end()
#define sz(x) ((int)(x).size())
#define maxz(x, y) x = max(x, y)
#define minz(x, y) x = min(x, y)
#define modz(x) x = x % mod + mod, x -= (x >= mod) * mod
#define mp(x, y) make_pair(x, y)
#define f first
#define s second
#define pii pair<int, int>
#define ordered_set(x) tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update> //less_equal
mt19937 rnd(time(nullptr));

const int N = 1e4 + 5, M = N * N, mod = 1e9 + 7;
const ld pi = acos(-1), eps = 1e-6;

int n, p[N], a[N], dp[N][N], done[N][N];
vector<int> e[N];

int solve(int u, int g);

void help(int u) {
    for (int i = 2; i < N; ++i) {
        int sum = 0;
        for (auto v: e[u]) if (v != p[u]) p[v] = u, sum += solve(v, i);
        done[u][i] = i + sum;
    }
}

int solve(int u = 0, int g = 0) {
    
    auto &me = dp[u][g];
    if (~me) return me;
    me = 1e4;
    
    if (gcd(a[u], g) != 1) {
        int sum = 0;
        for (auto v: e[u]) if (v != p[u]) p[v] = u, sum += solve(v, a[u]);
        minz(me, sum);
    }
    if (!~done[u][2]) help(u);
    for (int i = 2; i <= 2 * sz(e[u]); ++i) if (gcd(i, g) != 1) minz(me, done[u][i]);
    
    return me;
    
}

void hi() {
    
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v, e[--u].push_back(--v), e[v].push_back(u);
    }
    cout << solve();
    
}

void init() {
    fast;
    memset(dp, -1, sizeof dp), memset(done, -1, sizeof done);
    sieve();
}

signed main() {
    init();
    
    int T = 1;
    //cin >> T;
    for (int tc = 1; tc <= T; ++tc) hi();
    
    return 0;
}

answer.code: In function ‘void init()’:
answer.code:81:5: error: ‘sieve’ was not declared in this scope
   81 |     sieve();
      |     ^~~~~