python/TangDou/AcWing/Tree/1075.cpp

#include <bits/stdc++.h>
using namespace std;
const int N = 50010, M = N << 1;

int n;
int sum[N];
int d1[N], d2[N], st[N], res;

// 链式前向星
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

// 求树的直径模板
void dfs(int u) {
    st[u] = 1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (st[j]) continue;
        dfs(j);

        if (d1[j] + 1 >= d1[u]) {
            d2[u] = d1[u];
            d1[u] = d1[j] + 1;
        } else if (d1[j] + 1 > d2[u])
            d2[u] = d1[j] + 1;
    }
    res = max(res, d1[u] + d2[u]);
}

int main() {
    // 初始化
    memset(h, -1, sizeof h);
    cin >> n;

    // 筛法求约数和
    for (int i = 1; i <= n; i++)         // i是因数
        for (int j = 2; j <= n / i; j++) // j代表i的放大倍数 n/i不会溢出
            sum[i * j] += i;             // i*j的约数和+i

    // Q:为什么i=2开始，而不是i=1开始？
    // 答：因为题目要求 约数和小于原数，即sum[i]<i,如果i从1开始，就意味着sum[1]=0,表示1没有约数和
    // 也符合条件sum[1]=0<1,但这样加边的话，就是从0->1有一条边，图中树的根就是0号节点
    for (int i = 2; i <= n; i++)
        // 当约数和小于原数，添加一条由约数和到原数的边，有向边.小数->大数存在边
        // 无环:目标是原数，一个原数不可能存在多个不同的约数和
        // 所以，这是一棵树
        if (sum[i] < i) add(sum[i], i);

    // 万物初始总有起点，1就是起点
    dfs(1);

    // 输出
    cout << res << endl;

    return 0;
}