Untitled

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

#define ll 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 = 1e5 + 6, M = 20;

int inTime[N], outTime[N], timer, sz[N];
int a[N];
vector<int> freq[N], adj[N];
vector<int> divisors[N];

ll solve(int node, int p) {
    inTime[node] = ++timer;
    sz[node] = 1;
    freq[a[node]].push_back(timer);

    ll ans = 0;
    int cnt[2] = {};

    for (auto child: adj[node]) {
        if (child == p)continue;
        ans += solve(child, node);
        sz[node] += sz[child];

        int x = 0;

        for (auto d: divisors[a[node]]) {
            x += upper_bound(freq[d].begin(), freq[d].end(), outTime[child]) -
                 upper_bound(freq[d].begin(), freq[d].end(), inTime[child] - 1);
        }
        int y = sz[child] - x;
        ans += 1ll * x * (cnt[1] + cnt[0]) + 1ll * y * cnt[1];
        cnt[0] += y;
        cnt[1] += x;
    }


    outTime[node] = timer;
    return ans + sz[node];
}

void preprocess() {
    for (int i = 1; i < N; i++) {
        for (int j = i; j < N; j += i) {
            divisors[j].push_back(i);
        }
    }
}

void doWork() {
    int n;
    cin >> n;
    preprocess();
    for (int i = 1; i <= n; i++)cin >> 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);
    }
    cout << solve(1, 0);
}

int main() {
    IO
    int t = 1;

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