这道题之前可以用4e8左右的复杂度通过,现在加强了一发
好像有很多质数,我们只需要套用millerRobin就可以通过现在的数据了,但是其实还有办法卡,因为标算应该是还要加上pollardrho,我们只需要对于所有的质因数见一个树,实际上不用建出来,然后根据这个质因数在树上DFS,还是按照平常找直径的方法来搞,就可以了。
代码:
#include<bits/stdc++.h> using namespace std; #define debug(x) cerr<<#x<<" = "<<x #define sp <<" " #define el <<endl #define fgx cerr<<" ------------------------------------------------ "<<endl #define LL long long #define DB double #define mpt make_pair #define pb push_back inline int read(){ int nm=0; bool fh=true; char cw=getchar(); for(;!isdigit(cw);cw=getchar()) fh^=(cw=='-'); for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0'); return fh?nm:-nm; } #define M 200200 #define MAXN 32000 int n,to[M],nt[M],fs[M],tmp,pri[M],cnt,Hv,mx,pos,ans; bool f[M],g[M],vis[M]; vector<int>vec[M]; map<int,int>Rev; inline void link(int x,int y){to[++tmp]=y,nt[tmp]=fs[x],fs[x]=tmp;} inline void dfs(int x,int nd,int last=0){ if(nd>mx) mx=nd,pos=x; vis[x]=true; for(int i=fs[x];i;i=nt[i]) if((to[i]^last)&&g[to[i]]) dfs(to[i],nd+1,x); } namespace CALC2{ #define LDB long double inline LL mul(LL x,LL y,LL mod){ LL k=(LL)((LDB)x*(LDB)y/(LDB)mod); return ((x*y-k*mod)%mod+mod)%mod; } inline LL add(LL x,LL y,LL mod){return (x+y>=mod)?(x+y-mod):(x+y);} inline LL mns(LL x,LL y,LL mod){return (x-y<0)?(x-y+mod):(x-y);} inline LL qpow(LL x,LL sq,LL mod){ LL res=1; x%=mod; for(;sq;sq>>=1,x=mul(x,x,mod)) if(sq&1) res=mul(res,x,mod); return res; } } using namespace CALC2; namespace Miller_Rabin{ const LL pr[]={2,3,5,7,11,13}; inline bool isp(LL n){ if(n==1) return false; for(int i=0;i<6;++i){ if(n==pr[i]) return true; if(n<pr[i]) return false; if(n%pr[i]==0) return false; LL now=n-1,bas,las; int ct=0; while(!(now&1)) now>>=1,++ct; las=qpow(pr[i],now,n); for(int i=0;i<ct;i++,las=bas){ bas=mul(las,las,n); if(bas==1){ if(las==1||las==n-1) break; return false;} } if(bas!=1) return false; } return true; } } using Miller_Rabin::isp; int main(){ for(int i=2;i<=MAXN;i++){ if(!f[i]) pri[++cnt]=i,Rev[i]=cnt; for(int j=1;j<=cnt&&i*pri[j]<=MAXN;j++){ f[i*pri[j]]=true; if(i%pri[j]==0) break; } } Hv=cnt,n=read(); for(int i=1,x,y;i<n;i++) x=read(),y=read(),link(x,y),link(y,x); for(int i=1,x;i<=n;i++){ x=read(); if((x^1)&&!isp(x)){ for(int j=1;j<=cnt&&pri[j]*pri[j]<=x;j++) if(x%pri[j]==0){ while(x%pri[j]==0) x/=pri[j]; vec[j].pb(i); if(x==1||isp(x)) break; } } if(x>1){if(!Rev[x]) Rev[x]=++Hv; vec[Rev[x]].pb(i);} } for(int i=1;i<=Hv;i++){ for(int k=0,TP=vec[i].size();k<TP;k++) g[vec[i][k]]=true; for(int k=0,TP=vec[i].size(),x;k<TP;k++) if(!vis[x=vec[i][k]]) mx=0,dfs(x,1),mx=0,dfs(pos,1),ans=max(ans,mx); for(int k=0,TP=vec[i].size();k<TP;k++) vis[vec[i][k]]=g[vec[i][k]]=false; } printf("%d\n",ans);return 0; }