數字轉換 樹的最長鍊

連結：

https://www.acwing.com/activity/content/problem/content/1304/1/

題意：

• 如果一個數 x 的約數之和 y（不包括他本身）比他本身小，那麼 x 可以變成 y，y 也可以變成 x。例如，4 可以變為 3，1 可以變為 7。

  限定所有數字變換在不超過 n 的正整數範圍内進行，求不斷進行數字變換且不出現重複數字的最多變換步數

思路

• 每個點都有一個約數，相當于每個點都有一個父節點，構成幾顆樹
• 求這幾顆樹的最長鍊
• 求約數

代碼

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
const int N=2e5;
int e[N],ne[N],h[N],idx;
int n,sum[N];
bool st[N];
int ans;
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

int dfs(int u)
{
    int dist=0;
    int d1=0,d2=0;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        int d=dfs(j)+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;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++)
        for(int j=2;j<=n/i;j++)
            sum[i*j]+=i;
    for(int i=2;i<=n;i++)
        if(i>sum[i])
            add(sum[i],i),st[i]=true;
    for(int i=1;i<=n;i++)
        if(!st[i])
            dfs(i);
    cout<<ans<<endl;
    return 0;
}