最长树链（未解决）

虽然这道题我至今没有过，但是我还是决定先写一个博客来纪念（bushi / 记录）我那悲惨无奈的处境

最开始，我愚蠢地使用二维数组和floyed算法，不过别说运行了，直接变量空间过大，还是经验不足，也没有分析复杂度，即使运行了，也tmd铁定TLE ... 然后就将自己写了比较久的代码全部推翻，所以，在写之前要综合考虑时间和空间的复杂度，不要上来就写，以为写出来就万事大吉了，其实不过是莽撞而已

然后，依然没有分析时间复杂度，自以为是的写了比较好理解的bfs， 呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵， 50% ， nice ， TLE ， 再然后， 就用了枚举素数的方法，用网上的的到素数的方法，一个一个数试，好家伙，并用了树形DP 来求素数对应的那些树组成的森林中的每一棵树的直径，然后求出最大值，好家伙，62.5% ， 上帝是让我逼近于成功，但就是不让我成功，这是考验，呵呵

插曲：
看了题解大佬不满足于这水的数据（然鹅现实是我连这水一般的数据都过不了 ... ，，，），用了素性判断，以此来筛选出大素数，于是乎我又用了一段时间去了解米勒拉宾素性判断
中间用到了一些简单知识（不过我低效率的用了比较长的时间）：

数论中的拉格朗日定理

余式定理

AKS（确定性的）

不过据ksj大佬说，1e5的数据根本不需要使用素性判断，所以算是仅仅多学了点东西

于是，我又用了素数筛，来求这个森林，学了两个素数筛 ， 最后用了线性筛，不过好像没多大用 ... 我又分别用unordered_map and map 分别来试，不过没多大差别（两种map性能比较），最终都是 75%

现在想先放一放，不想这样耗下去了,目前的代码：

//https://ac.nowcoder.com/acm/problem/13233
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LOCAL
using namespace std;
const int maxn=1e5+10;
const int INF=1e5;
vector link[maxn];
int val[maxn];
unordered_map> mp;
int dp[maxn];   // 在该树中离这一点最远的距离
int mark[maxn];
int ans=1;
// vector primes;
int primes[maxn];int cont=0;
int isnp[maxn]={0};
int read(){
    int s=0,f=1,c=getchar();
    while (c<'0' || c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0' && c<='9') { s=s*10+c-'0';c=getchar();}
    return s*f;
}
// 先用最简单的埃氏筛 (后来证明不行)
// void getprime(){
//     for (int i=2;i<=4e4;++i){
//         if (!isnp[i]){
//             for (int j=i*i;j<=4e4;j+=i){
//                 isnp[j]=1;
//             }
//             primes.push_back(i);
//         }
//     }
// }

// 然后使用线性筛
// void getprime(){
//     for (int i=2;i<=4e4;++i){
//         if (!isnp[i]) primes.push_back(i);
//         for (int j=0;j<(int)primes.size();++j){
//             if (primes[j]*i>4e4) break;
//             isnp[i*primes[j]]=1;
//             if (i%primes[j]==0) break;
//         }
//     }
// }
void getprime(){
    // int cont=0;
    for (int i=2;i<=4e4;++i){
        if (!isnp[i]) primes[++cont]=i;
        for (int j=1;j<=cont;++j){
            if (primes[j]*i>4e4) break;
            isnp[i*primes[j]]=1;
            if (i%primes[j]==0) break;
        }
    }
}

//wait
int gcd(int a,int b)
{
    while(b^=a^=b^=a%=b);
    return a;
}
//quick_pow has mod generally, or it will overflow  ;  when mod==0  ,  mod doesn't exist 
int quick_pow(int d, int z,int mod){
    // if (!z) return 1;
    int rs=1;
    while(z){
        if (z&1) {rs*=d;if (mod) rs%=mod;}
        z>>=1;
        d*=d;
        if (mod) d%=mod;
    }
    return rs;
}
/*
米勒罗宾素性判断：
（1）计算奇数M，使得N=2^r * M + 1；

（2）选择随机数A>=1;++r;}
    for (int i=0;i<5;++i){
        int A=rand()%(N-2)+2;
        int B=quick_pow(A,M,N);
        if (B==1) continue;       
        for (int i=0;ia;
    if(val[u]%num!=0)    return 0;
    mark[u]=1;int res=1;
    for(int x:link[u])
    {
        if(!mark[x])
        {
            int Cnt=dp_dfs(x,num);
            res=max(res,1+Cnt);
            ans=max(ans,res);
            a.push_back(Cnt);
        }
    }sort(a.begin(),a.end());
    int x=a.size();
    if(x>1)   ans=max(ans,a[x-1]+a[x-2]+1);
    return res;
}
int main(){
    #ifdef LOCAL
    freopen("input.txt","r",stdin);
    #endif
    srand((unsigned int)time(NULL));
    getprime();
    int n=read();
    for (int i=1;i 积
        if (miller_rabbin(pdct)) {
            mp[pdct].push_back(i);
            continue;
        }
        // for (int j=2;j*j<=pdct;++j){    // 这里可以简化，可以先得到素数表，然后根据表中的素数来遍历查询，因为数越大，素数越离散，浪费的时间越多

        // for (int j:primes){
        //     if (j*j<=pdct){
        //         if (pdct%j==0){
        //             while(pdct%j==0) pdct/=j;
        //             mp[j].push_back(i);
        //         }
        //     }
        // }
        for (int j=1;j<=cont && primes[j]*primes[j]<=pdct;++j){
            if (pdct%primes[j]==0){
                while(pdct%primes[j]==0) pdct/=primes[j];
                mp[primes[j]].push_back(i);
            }
        }
        if (pdct>1) mp[pdct].push_back(i);
    }
    for (unordered_map>::iterator p=mp.begin();p!=mp.end();++p){
        // for (int i=0;i<(int)p->second.size();++i) if (mark[p->second[i]]==0) dp_dfs(p->second[i],p->first);
        for (int j:p->second) if (mark[j]==0) dp_dfs(j,p->first);
        // for (int i=0;i<(int)p->second.size();++i) mark[p->second[i]]=0;
        for (int j:p->second) mark[j]=0;
    }
    // printf("%d",ans+1);
    printf("%d",ans);
    return 0;
}

-----------------------------------10-11-------------------------------------------