线性筛求最小质因数+质因数分解+树形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;

题目内容

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

输入描述

第一行输入一个整数$n$($2≤n<10^5$)，表示树的节点数。 第二行输入$n$个整数$a_1,a_2,...,a_n$($1≤a_i≤10^7$)，表示每个节点的权值。 此后$n-1$行,第$i$行输入两个整数$u_i$和$v_i$($1≤u_i,vi≤n; u_i≠v_i$)表示树上第$i$条边连接节点$u_i$和$v_i$。保证树联通，没有重边。

输出描述

先输出一个整数，表示最少需要操作的次数。 如果需要的操作次数不为零，接下来一行，从小到大输出若干整数，表示每次操作选择的点。

样例1

输入

6
2 2 3 4 30 6
1 2
2 3
2 4
1 5
5 6

输出

2
3 4

说明

$6$个点的权值质因子个数分别为[$1,1,1,1,3,2$]，所以需要染色的边为($1,2$),($2,3$),($2,4$)，最少需要操作$2$次，先选择$3$号点，再选择$4$号点。