数字转换（树形DP）

如何对一个问题挖掘信息把它变成已知的问题十分重要，这一题恰恰体现这一点：

https://www.acwing.com/problem/content/1077/

首先，对于一个数x，它对应一个其约数之和y，同时他们可以相互转换，于是我们可以给他们连一条边。

这样子，1--n的数就抽象成图中的点，我们进一步看看约数之和<自己的条件，这就避免了出现回路：假如有A,B,C构成一个回路，那么令A的约数之和为B，B的约数之和为C，那么A只能是C的约数之和，于是A>B>C>A,矛盾

于是整个图就可以抽象成森林。问题就是求每一个树的最大转换次数，也就是求最长链这一经典问题。

考虑n<50000，直接暴力枚举肯定TLE，我们可以参考毕业季那题从因子出发枚举它倍数即可（nlogn)

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
int n;
int a[500010];
int vis[500010];
int ans=0;
int res=0;
vector<int> edge[500010];
int dfs(int root,int fa){
    vis[root]=1;
    int dist = 0; // 表示从当前点往下走的最大长度
    int d1 = 0, d2 = 0;
    for (int i = 0; i<edge[root].size(); i++)
    {
        int j = edge[root][i];
        if (j == fa) continue;
        int d = dfs(j, root) + 1;
        dist = max(dist, d);
        if (d >= d1) d2 = d1, d1 = d;
        else if (d > d2) d2 = d;
    }
    ans = max(ans, d1 + d2);
    return dist;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int k=2;k*i<=n;k++){
            a[k*i]+=i;
        }
    }
    
    for(int i=2;i<=n;i++){
        if(a[i]>=i) continue;
        edge[i].push_back(a[i]);
        edge[a[i]].push_back(i);
    }
    for(int i=2;i<=n;i++){
        if(vis[i]) continue;
        ans=0;
        dfs(i,-1);
        res=max(res,ans);
    }
    cout<<res;
}