线性筛求最小质因数+质因数分解+树形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;
bool st[N];
int a[100005];
int n;
vector<int>g[100005];
void get_primes(int n)
{
	for(int i = 2 ; i <= n ; i++)
	{
		if(!st[i]) minp[i] = i,primes[cnt++] = i;
		for(int j = 0 ; primes[j] * i <= n ;j++)
		{
			int t = primes[j] * i;
			st[t] = true;
			minp[t] = primes[j];
			if(i % primes[j] == 0) break;
		}
	}
}
int get(int x){
	set<int>s;
	while(x>1){
		s.insert(minp[x]);
		x/=minp[x];
	}
	int res=s.size();
	return res;
}
int dp[100005];
void dfs1(int u,int fa){
	for(int v:g[u]){
		if(v==fa) continue;
		dfs1(v,u);
		if(a[v]==a[u]){
			dp[v]=1;
		}
	}
}
vector<int>ans;
void dfs2(int u,int fa){
	int res=0;
	for(int v:g[u]){
		if(v==fa) continue;
		dfs2(v,u);
		res|=dp[v];
	}
	if(dp[u]==1){
		if(res==0)
			ans.push_back(u);
	}
	if(res==1){
		dp[u]=1;
	}
}
signed main() {
	get_primes(10000000);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i]=get(a[i]);
	}
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs1(1,0);
	dfs2(1,0);
	cout<<ans.size()<<'\n';
	sort(ans.begin(),ans.end());
	for(int v:ans){
		cout<<v<<' ';
	}
	cout<<'\n';
	return 0;
}

题目内容

小红有一棵$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$号点。