AcWing 1075. 数字转换

题目传送门

#include 

using namespace std;
const int N = 50010;

int n;
int sum[N];
int h[N], e[N], ne[N], idx;
int d1[N], d2[N], res;

//邻接表模板
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

//求树的直径
void dfs(int u) {
    if (d1[u]) return;  //记忆化搜索
    for (int i = h[u]; ~i; i = ne[i]) { //遍历每条出边
        int j = e[i];
        dfs(j);                       //计算子节点的最大长度
        //如果子节点j的最大长度+1,可以更新u节点的最大长度
        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;

    //求约数和的经典办法[模板] 比试除法的效率要高
    //求2到n中每一个数的因数和，1不算是因为题意
    for (int i = 1; i <= n; i++)//i是因数
        for (int j = 2; j <= n / i; j++)//j代表i的放大倍数
            sum[i * j] += i; //i*j的约数和+i

    //构建森林
    //从 1 开始会添加一条从 0 到 1 的边
    for (int i = 2; i <= n; i++)
        if (sum[i] < i)          //当约数和小于原数，添加一条由约数和到原数的边，有向边
            add(sum[i], i);
    /**
     Q:我感觉这个add应该加两条边吧
     A:小的数字往大的数字上连一条就够了
     搜了根，这个树的直径就找出来了，没有反向搜的必要
     */

    //建好图后，本题就 等价于 找出一个森林中，直径最长 的树，
    //并求出该树的 直径, 其实我们找以1为根的树, 单单求这颗树的直径就是答案.
    dfs(1);

    //遍历每个节点,求树的直径
    //for (int i = 1; i <= n; i++) dfs(i);

    //输出
    printf("%d\n", res);
    return 0;
}