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

vector<int> primes;
const int P = 25;

int main() {
	cin.tie(0)->sync_with_stdio(0);

	for (int i = 2; i <= 100; i++) {
		bool prime = 1;
		for (int j = 2; prime and j*j <= i; j++)
			prime &= i%j != 0;
		if (prime) primes.emplace_back(i);
	}

	int n; cin >> n;
	vector<int> a(n); for (int &v : a) cin >> v;

	vector adj(n, vector<int>());
	for (int i = 1; i < n; i++) {
		int a, b; cin >> a >> b; a--, b--;
		adj[a].emplace_back(b);
		adj[b].emplace_back(a);
	}

	vector dp(n, vector<int>(primes.size(), INT_MAX));
	auto dfs = [&](auto self, int u, int p) {
		if (adj[u].size() == 1 and adj[u][0] == p) {
			for (unsigned i = 0; i < primes.size(); i++) {
				if (gcd(primes[i],a[u]) > 1) dp[u][i] = 0;
				else dp[u][i] = primes[i];
			}
			return;
		}

		map<int,int> cur {{1, 0}, {a[u], 0}};

		for (int v : adj[u]) if (v != p) {
			self(self, v, u);

			map<int,int> cur2;
			auto add = [&](int b, int c) {
				if (cur2.count(b)) cur2[b] = min(cur2[b],c);
				else cur2[b] = c;
			};
			for (auto [i, c] : cur) {
				for (unsigned j = 0; j < primes.size(); j++) {
					if (i % primes[j]) {
						if (i * primes[j] <= 10000)
							add(i*primes[j], c + dp[v][j]);
					} else add(i, c + dp[v][j]);
				}
			}
			swap(cur,cur2);
		}

		for (auto [i, c] : cur)
			for (unsigned j = 0; j < primes.size(); j++)
				if (i % primes[j] == 0)
					dp[u][j] = min(dp[u][j], c + i * (i != a[u]));
	};
	dfs(dfs, 0, 0);

	cout << *min_element(dp[0].begin(), dp[0].end()) << '\n';
}