链接：F - 孤独的树
题意：
给定一棵树，每次操作可以消去一个节点权值的质因子，求最小操作次数，使得树上相邻节点互质。
做法：
质因子之间互不影响，所以是可以分开看的。
如果只考虑消去某个质因子 k ，d[i][0]为不操作这个节点，使得其与子节点互质，d[i][1]为操作这个节点，使得与子节点互质。
就有转移方程：
d[x][0] += d[y][1];
d[x][1] += min(d[y][0], d[y][1]);
d[x][1] += calc(a[x], k);
从1~n遍历所有节点，如果a[i]不为1的话，就一定有可去除的质因子，那就以i为根开始进行dp，一边dp一边消去这个质因子就好了。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7;
int p[N];
int f[N];
int init(int n)
{
int cnt = 0;
for (int i = 2; i <= n; i++)
{
if (f[i] == 0)
{
f[i] = i;
p[++cnt] = i;
}
for (int j = 1; j <= cnt; j++)
{
if (p[j] > f[i] || p[j] * i > n) break;
f[i * p[j]] = p[j];
}
}
return cnt;
}
vector<int> v[N];
int d[N][2], a[N];
int calc(int &n, int p)
{
int ret = 0;
while(n % p == 0)
{
n /= p;
ret++;
}
return ret;
}
void dfs(int x, int fa, int p)
{
d[x][0] = d[x][1] = 0;
for (auto i : v[x])
{
int y = i;
if (y == fa) continue;
if (a[y] % p) continue;
dfs(y, x, p);
d[x][0] += d[y][1];
d[x][1] += min(d[y][0], d[y][1]);
}
d[x][1] += calc(a[x], p);
}
void solve()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
for (int i = 1; i <= n - 1; i++)
{
int x, y;
scanf("%lld%lld", &x, &y);
v[x].emplace_back(y);
v[y].emplace_back(x);
}
init(100000);
int ans = 0;
for (int i = 1; i <= n; i++)
{
while(a[i] > 1)
{
dfs(i, 0, f[a[i]]);
ans += min(d[i][0], d[i][1]);
}
}
cout << ans;
}
signed main()
{
int tt = 1;
// cin >> tt;
while (tt--) solve();
return 0;
}
