每日一题 最长树链 题解

这道题之前可以用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;
}