算法分析

• 1、如果一个数 x 的约数之和 y（不包括他本身）比他本身小,则x与y连一条边，问题转化为求树的直径问题

• 2、由于只用到y到x的边，因此只需要连一条从y到x的有向边即可，但必须从当前树的最小的数(树根)开始向下递归

• 3、由于题目可能会存在多棵树，因此需要st[]数组标记该点是否被遍历过
  (其中这里只有一棵以1为根结点的树，只需要dfs(1)即可，原因是啥没证明出来)

时间复杂度 $O(nlogn)$

//通过筛法求出1到n的所有约数之和
for(int i = 1;i <= n;i ++) //O(n)
{
    for(int j = 2;j <= n / i;j ++) // 调和级数O(logn) = n + n / 2 + n / 3 + ... + n/n = lnn + c
    {
        sum[i * j] += i;
    }
}

参考文献

算法提高课

Java 代码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N = 50010;
    static int M = N;
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static int idx = 0;
    static int[] sum = new int[N];//sum[i]表示i的约数之和
    static boolean[] st = new boolean[N];
    static int ans = 0;
    static void add(int a,int b)
    {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    //找到u点往下走的最大长度
    static int dfs(int u)
    {
        st[u] = true;
        int d1 = 0;
        int 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 = Math.max(ans, d1 + d2);
        return d1;
    } 

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        Arrays.fill(h, -1);
        //通过筛法求出1到n的所有约数之和
        for(int i = 1;i <= n;i ++)
        {
            for(int j = 2;j <= n / i;j ++)
            {
                sum[i * j] += i;
            }
        }
        for(int i = 1;i <= n;i ++)
            if(sum[i] < i)
            {
                add(sum[i],i);
            }
        for(int i = 1;i <= n;i ++)
        {
            if(!st[i])
                dfs(i);
        }
        System.out.println(ans);
    }
}

只递归根结点是1的树

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N = 50010;
    static int M = N;
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static int idx = 0;
    static int[] sum = new int[N];//sum[i]表示i的约数之和
    static int ans = 0;
    static void add(int a,int b)
    {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    //找到u点往下走的最大长度
    static int dfs(int u)
    {
        st[u] = true;
        int d1 = 0;
        int 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 = Math.max(ans, d1 + d2);
        return d1;
    } 

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        Arrays.fill(h, -1);
        for(int i = 1;i <= n;i ++)
        {
            for(int j = 2;j <= n / i;j ++)
            {
                sum[i * j] += i;
            }
        }
        for(int i = 1;i <= n;i ++)
            if(sum[i] < i)
            {
                add(sum[i],i);
            }
        dfs(1);
        System.out.println(ans);
    }
}