$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路：

1. 从倍数角度出发，让 i 的倍数的 sum[i * j] 加上 i
2. 每个 i 只会有一个 sum[i]，即 sum[i] 是 i 的父节点
3. 最后就是求一个树的直径

可参考： 树的最长路径

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 50010;

int n;
int sum[N];
int h[N],e[N],ne[N],idx;
int ans;

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

int dfs(int u)
{
    int d1=0,d2=0;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        int d=dfs(j)+1;
        if(d>=d1) d2=d1,d1=d; 
        else if(d>d2) d2=d; 
    }

    ans=max(ans,d1+d2); //更新最大值

    return d1;
}

int main()
{
    cin>>n;

    for(int i=1;i<=n;i++)
        for(int j=2;j<=n/i;j++)
            sum[i*j]+=i;

    memset(h,-1,sizeof h);

    for(int i=2;i<=n;i++)
        if(sum[i]<i)
            add(sum[i],i); // i 的约数之和向 i 连一条边

    dfs(1);

    cout<<ans<<endl;

    return 0;
}