Untitled

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

vector<int> discover;
vector<vector<int>> adj(1006);
int n;

void add_divisors(int n, map<int, int>& m) {
    int i = 2;
    while (i * i <= n) {
        while (n % i == 0) {
            m[i]++;
            n /= i;
        }
        ++i;
    }
    if (n > 1) m[n]++;
}

int val[1005];
vector<int> par(1005, -1); // Initialisation à -1 pour les parents non définis

void dfs(int node, int p = 0) { // Parent initialisé à -1
    discover.push_back(node);
    par[node] = p;
    for (auto t : adj[node]) {
        if (t == p) continue;
        dfs(t, node);
    }
}

vector<int> mask(1005);

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> val[i];
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        u--; v--;  // Convertir en index 0
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    bool ok=true;
    dfs(0);  // Effectuer un DFS à partir du nœud 0

    map<int, int> m;
    for (int i = 0; i < n; ++i) {
        map<int, int> ps;
        add_divisors(val[i], ps);
        for (auto t : ps) {
            ok=false;
            m[t.first] = max(m[t.first], t.second);
        }
    }
    if (ok)
    {
        cout<<0;
        return 0;
    }
    for (int i = 0; i < n; ++i) {
        int maski = 0;
        int k = 0;
        map<int, int> ps;
        add_divisors(val[i], ps);
        for (auto t : m) {
            if (t.second == ps[t.first]) {
                maski += (1 << k);
            }
            k++;
        }
        mask[i] = maski;
    }

    reverse(discover.begin(), discover.end());

    int output = n;
    vector<vector<int>>dp(n+5,vector<int>(1005,1008));
    int goal = (1 << m.size()) - 1;
    for (int i = 0; i < n; ++i) {
        int node = discover[i];
        dp[node][mask[node]] = 1;
        dp[node][0] = 1;
        for (auto t : adj[node]) {
            if (t == par[node]) continue;
            auto v=dp[node];
            for (int mask = goal;mask>=0;mask--)
            {
                for (int x=goal;x>=0;x--)
                {
                    v[mask|x]=min(v[mask|x],dp[node][mask]+dp[t][x]);
                }
            }
            dp[node]=v;
        }
        output = min(output, dp[node][goal]);
    }

    cout << output ;

    return 0;
}