题目传送门思路很明显每次暴力往上跳最坏情况下是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 代码#includebits/stdc.husingnamespacestd;#definefile_in(s)freopen(s.in,r,stdin);#definefile_out(s)freopen(s.out,w,stdout);#definefile(s)file_in(s)file_out(s)usinglllonglong;usingullunsignedlonglong;templatetypenameT,typenameComparelessTusingheappriority_queueT,vectorT,Compare;constintINF0x3f3f3f3f;constll INFLL0x3f3f3f3f3f3f3f3fLL;constintMOD1e97;constdoubleEPS1e-8;constintN5e55,M1e75;intn,cnt0,a[N],ans[N],pri[M];bitsetMp;vectorintvec[N];voideuler_sieve(){// 欧拉筛p.reset();p[0]p[1]true;for(inti2;iM-5;i){if(!p[i])pri[cnt]i;for(intj1;jcnti*pri[j]M-5;j){p[i*pri[j]]true;if(i%pri[j]0)break;}}}voiddfs(intu,intf){for(intv:vec[u]){// 遍历儿子if(vf)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();// 千万不要忘记漏写这一行cinn;for(inti1;in;i)cina[i];for(inti1,u,v;in;i){cinuv;vec[u].push_back(v);vec[v].push_back(u);}dfs(1,0);// 开始递归for(inti1;in;i)cout(!ans[i]?-1:ans[i]) ;// 输出结果return0;}完结撒花 ✿✿ヽ(°▽°)ノ✿