题意分析：

给出一棵树，对于该树上的每个节点都有自己的权值，然后可以通过对某个权值进行除以他的质因子值的操作，求最少的操作次数，能使整棵树相邻的两个节点的权值公约数都为1；

个人思路 ：

首先，众所周知，小白月赛最后一题只要是树，那都是树形dp(bushi),很容易想到定义dp为以i为根子树的节点的某些性质，这个性质要求能够从下往上进行传递更新，然后考虑对于儿子节点是叶子节点的最下父节点的权值更新，对于该父节点来说，要求和父父节点，儿子节点的公约数都为1，那我可不可以更新父节点的权值，因为如果更新子节点（当前为叶子节点）的权值的话，肯定不如更新父节点来的划算，因为父节点还可能有儿子节点和父父节点，所以更新来做到满足题意，然后就考虑怎么样能够最小化操作次数，那么我选择用父亲节点的权值对于两个节点的的最大公约数进行除，这样是一定能使最小的，那么最小操作次数又是怎么能计算呢，由于权值的最大值只有1e5,那我就暴力的计算，对于两个点的最大公约数进行质因数分解，就得到这个最大公约数的质因子的个数，然后就得到最小的操作次数，这样预处理出质数，并且预处理出1-1e5的每个数的质因数个数，然后从下往上更新即可。

复杂度证明

首先是预处理的复杂度:

  1. 求出质数的时间复杂度是O（n）;
  2. 求出每个数的质因数个数的时间复杂度为O（n*sqrt(n)）; 3.然后就是dfs遍历整棵树的时间复杂度是O（n）, 所以是能过得，接下来贴上我的代码:
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int prime[maxn],vis[maxn];
int cnt = 0;
int res[maxn];
void pre() {
	vis[1] = 1;
	for (int i = 2; i <= maxn - 10; ++i) {
		if (!vis[i]) {
			prime[cnt++] = i;
		}
		for (int j = 0; j < cnt && prime[j] * i <= maxn - 10; ++j) {
				vis[i*prime[j]] = 1;
				if (i % prime[j] == 0) break;
		}
	}
	res[1] = 0;
	for (int i = 2; i <= maxn - 10; ++i) {
		if (!vis[i]) {
			res[i] = 1;
		}
		else {
			int n = i;
			for (int j = 2; j <= n / j; j++) {
				if (n % j == 0) {
					while (n % j == 0) {
						n /= j;
						res[i]++;
					}
				}
			}
			if (n > 1) res[i]++;
		}
	}
}
int val[maxn];
int head[maxn * 2], to[maxn * 2], nex[maxn * 2];
int tot;
void add(int u, int v) {
	to[++tot] = v;
	nex[tot] = head[u];
	head[u] = tot;
}
int dp[maxn];
int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b,a%b);
}
void dfs(int fa, int son) {
	for (int i = head[son]; i; i = nex[i]) {
		int v = to[i];
		if (v == fa) continue;
		dfs(son, v);
		int num = gcd(val[son], val[v]);
		val[son] /= num;
		dp[son] += res[num]+dp[v];
	}
}
int main()
{
	pre();
	int n;
    std::ios::sync_with_stdio(0);
	cin>>n;
	for (int i = 1; i <= n; ++i)
		cin>>val[i];
	int u, v;
	for (int i = 2; i <= n; ++i) {
		cin>>u>>v;
		add(u, v);
		add(v, u);
	}
	dfs(0, 1);
	cout<<dp[1]<<'\n';
	return 0;
}