思路与算法

先筛出1..n每个数的真约数和sum[x]：枚举约数d，将它累加给2d、3d等倍数，因而不会把x自身计入sum[x]。

仅当1≤sum[x]<x时，连接x和sum[x]。若把较小者视为父亲，每个点最多有一个父亲，且父节点编号严格减小，因此得到若干棵树。任意不重复的变换序列就是森林中的一条简单路径，答案是各树直径的最大边数。

不必显式存储邻接表。按编号从n递减到1处理，子节点必已处理完；维护每点最长、次长的两条向下分支。经过x的最长路径长度为first[x]+second[x]，用其更新答案。若x有合法父亲，将first[x]+1作为父亲的一条新分支，更新父亲的前两大值。

正确性说明

筛法恰好把每个严格小于x的正约数加给x，故真约数和正确。每条转换边都由较大的端点指向唯一较小的父亲；若存在无向环，环上最大编号点必须有两个更小的相邻点，与其只有一个父亲矛盾，所以图是森林。

树中任何简单路径都在某个最高点处分成至多两条不同孩子分支。递减处理时该点的全部孩子已将各自最长分支传来，前两大分支之和就是以该点为最高点的最长路径。枚举所有最高点以及所有树，得到全森林的最长简单路径，其边数即最多转换步数。

复杂度

约数和数组及两条分支数组初始化O(n)。筛法访问总次数为O(n log(n+1))，递减聚合O(n)。总时间O(n log(n+1))，空间O(n)。无需邻接表或递归栈。

易错点

1的真约数和为0，但0不在允许的正整数范围内，不能连到0。完全数的约数和等于自身，也不能加自环；约数和大于自身时同样不连边。答案统计边数而非点数，n=1应输出0。图可能有多棵树，不能只计算包含1的连通分量。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> sum(n + 1), first(n + 1), second(n + 1);
    for (int d = 1; d <= n / 2; ++d)
        for (int x = d * 2; x <= n; x += d)
            sum[x] += d;
    int answer = 0;
    for (int x = n; x >= 1; --x) {
        answer = max(answer, first[x] + second[x]);
        int p = sum[x];
        if (p > 0 && p < x) {
            int length = first[x] + 1;
            if (length > first[p]) {
                second[p] = first[p];
                first[p] = length;
            } else if (length > second[p])
                second[p] = length;
        }
    }
    cout << answer << '\n';
}