题解 | #孤独的树#

对于每种质因子取出包含这个质因子的点的导出子图，这个子图一定是一个森林，现在要做的是删除森林中的若干个节点，使得没有任意两个节点之间有边相连，删除节点的代价是这个质因子的指数，这个直接对每棵树做一遍简单树形dp即可。

由于每个数最多包含 $O(\log va{l}_i)O(\backslash log\; val\_i)$ 种不同的质因子因此复杂度是对的，为 $O(W+n\log W)O(W\; +\; n\; \backslash log\; W)$。

#include <bits/stdc++.h>

const int Maxn = 1e5 + 5;

int pri[Maxn], cp; int mpf[Maxn];
void sieve() {
	for(int i = 2; i <= 100000; ++i) {
		if(!mpf[i]) pri[++cp] = i, mpf[i] = i;
		for(int j = 1; j <= cp && pri[j] <= 100000 / i; ++j) {
			mpf[i * pri[j]] = pri[j];
			if(i % pri[j] == 0) break;
		}
	}
}

int n, a[Maxn], x, y; std::vector<int> g[Maxn];
bool vis[Maxn];
std::vector<int> rt[Maxn];

int f[Maxn][2];

void dfs(int u, int fa, int p) {
	int z = a[u], c = 0; vis[u] = 1;
	while(z % p == 0) ++c, z /= p;
	f[u][0] = c, f[u][1] = 0;
	for(int v : g[u]) {
		if(a[v] % p || v == fa || vis[v]) continue;
		dfs(v, u, p);
		f[u][0] += std::min(f[v][0], f[v][1]);
		f[u][1] += f[v][0];
	}
}

int main() {
	sieve();
	std::cin >> n;
	for(int i = 1; i <= n; ++i) {
		std::cin >> a[i];
		x = a[i];
		while(x > 1) {
			rt[mpf[x]].emplace_back(i);
			x /= mpf[x];
		}
	}
	for(int i = 1; i < n; ++i) {
		std::cin >> x >> y;
		g[x].emplace_back(y);
		g[y].emplace_back(x);
	}
	int ans = 0;
	for(int i = 1; i <= cp; ++i) {
		for(int u : rt[pri[i]]) vis[u] = 0, f[u][0] = f[u][1] = 0;
		for(int u : rt[pri[i]]) if(!vis[u]) dfs(u, 0, pri[i]), ans += std::min(f[u][0], f[u][1]);
	}
	std::cout << ans;
}