题目内容

小塔有一棵$n$个节点的树，$1$号节点是树的根节点。$i$号节点的权值为$a_i$，如果边($u,v$)的两个端点权值的质因子个数相同，那么这条边需要被染色。例如，$6$有两个质因子，分别是$2$和$3，4$只有一个质因子$2$。 小塔每次可以选择一个点，将这个点到根节点的所有边染色，请问最少需要操作多少次，才能使得所有需要被染色的边都被染色。

线性筛求最小质因数+质因数分解+树形dp

对于求出某个数的质因数的个数，普通的质因数分解的时间复杂度为sqrt(N)，加上有n个数，时间很极限，那么加个线性筛预处理一下每个数的最小质数把质因数分解变成log级别的，第一遍树形dp把哪些边需要染色求出来，第二遍树形dp求出最小次数以及染色哪几个点即可详细实现可见代码。

代码如下

cpp

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e7 + 100;
int primes[N],minp[N],cnt;