当前位置：首页 > news >正文

[入门赛 #49] GPA 计算？题解

news 2026/7/13 1:45:17

题目传送门

思路

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

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

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

好了废话不多说上代码。

AC 代码

#include<bits/stdc++.h>usingnamespacestd;#definefile_in(s)freopen(s".in","r",stdin);#definefile_out(s)freopen(s".out","w",stdout);#definefile(s)file_in(s)file_out(s)usingll=longlong;usingull=unsignedlonglong;template<typenameT,typenameCompare=less<T>>usingheap=priority_queue<T,vector<T>,Compare>;constintINF=0x3f3f3f3f;constll INFLL=0x3f3f3f3f3f3f3f3fLL;constintMOD=1e9+7;constdoubleEPS=1e-8;constintN=5e5+5,M=1e7+5;intn,cnt=0,a[N],ans[N],pri[M];bitset<M>p;vector<int>vec[N];voideuler_sieve(){// 欧拉筛p.reset();p[0]=p[1]=true;for(inti=2;i<=M-5;i++){if(!p[i])pri[++cnt]=i;for(intj=1;j<=cnt&&i*pri[j]<=M-5;j++){p[i*pri[j]]=true;if(i%pri[j]==0)break;}}}voiddfs(intu,intf){for(intv: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);// 递归儿子}}signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);euler_sieve();// 千万不要忘记漏写这一行cin>>n;for(inti=1;i<=n;i++)cin>>a[i];for(inti=1,u,v;i<n;i++){cin>>u>>v;vec[u].push_back(v);vec[v].push_back(u);}dfs(1,0);// 开始递归for(inti=1;i<=n;i++)cout<<(!ans[i]?-1:ans[i])<<" ";// 输出结果return0;}