考点

树的最长路径问题：https://www.acwing.com/problem/content/1074/

思路：

1. 预处理出1 ~ n 范围中所有数的约数之和（处理方法参考埃氏筛法的求约数的方法）
2. 从题上可以知道，当前数的约数之和是要小于当前数的值。然后再把当前这个数的约数之和指向当前数
3. 因为，可能存在多个根（没有（约数之和）的数称为根）森林
4. dfs从当前根出发

#include <iostream>
#include <cstring>

using namespace std;
int n;
const int N = 50010;
int h[N], e[N], ne[N], idx;
int sum[N], ans;
bool st[N];

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 != -1; 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(void)
{
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++)
        for (int j = 2; j <= n / i; j ++)
            sum[i * j] += i;

    for (int i = 2; i <= n; i ++)
        if (i > sum[i])
        {
            add(sum[i], i);
            st[i] = true;
        }

    for (int i = 1; i <= n; i ++)
        if (!st[i])
            dfs(i);
    cout << ans << endl;
    return 0;
}