题目传送门

思路

很明显，每次暴力往上跳最坏情况下是 $O(n^2)$ 的，显然不可取。

那么我们怎么快速统计结点 $i$ 到根节点 $1$ 的路径之间的素数点权最大值呢？我们可以开一个最大值数组 ans 来存储结果，然后从根节点开始递归，遍历当前节点的儿子，儿子的 ans 值先继承当前节点的 ans 值，如果当前节点的点权是素数的话，那么儿子节点的 ans 值还要与当前点权进行比较取最大值。这样我们就只用一遍 dfs 就完成了，复杂度是 $O(n)$。

这样子就完了吗？还没有。$v_i$ 最大可以达到 $10^7$ ，每次 $O(\sqrt{n})$ 判断素数明显会炸，所以我们要预先跑一遍欧拉筛然后再判断就可以避开 TLE 了。

好了废话不多说上代码。

AC 代码

#include<bits/stdc++.h>
using namespace std;
#define file_in(s) freopen(s".in","r",stdin);
#define file_out(s) freopen(s".out","w",stdout);
#define file(s) file_in(s) file_out(s)
using ll=long long;
using ull=unsigned long long;
template<typename T,typename Compare=less<T>>
using heap=priority_queue<T,vector<T>,Compare>;
const int INF=0x3f3f3f3f;
const ll INFLL=0x3f3f3f3f3f3f3f3fLL;
const int MOD=1e9+7;
const double EPS=1e-8;
const int N=5e5+5,M=1e7+5;
int n,cnt=0,a[N],ans[N],pri[M];
bitset<M> p;
vector<int> vec[N];
void euler_sieve(){// 欧拉筛
	p.reset();
	p[0]=p[1]=true;
	for(int i=2;i<=M-5;i++){
		if(!p[i]) pri[++cnt]=i;
		for(int j=1;j<=cnt&&i*pri[j]<=M-5;j++){
			p[i*pri[j]]=true;
			if(i%pri[j]==0) break;
		}
	}
}
void dfs(int u,int f){
	for(int v:vec[u]){// 遍历儿子
		if(v==f) continue;// 如果是父亲就跳过
		ans[v]=ans[u];// 继承 ans[u]
		if(!p[a[u]]) ans[v]=max(ans[v],a[u]);// 如果 a[u] 是素数，就与 ans[v] 比较取最大值
		dfs(v,u);// 递归儿子
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	euler_sieve();// 千万不要忘记漏写这一行
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1,u,v;i<n;i++){
		cin>>u>>v;
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
	dfs(1,0);// 开始递归
	for(int i=1;i<=n;i++) cout<<(!ans[i]?-1:ans[i])<<" ";// 输出结果
	return 0;
}

完结撒花 ✿✿ヽ(°▽°)ノ✿