Description
如果一个数x的约数和（不包括它本身，下同）比它本身小，那么x可以变成它的约数和；如果对于某个y>x且y的约数和为x，那么x也可以变成y。例如，4可以变为3，1可以变为7。限定所有的数字变换在不超过n的正整数范围内进行，求不断进行数字变换且没有重复数字出现的最多变换步数。
Input
输入一个正整数n
Output
输出不断进行数字变换且没有重复数字出现的最多变换步数。
Sample Input
7
Sample Output
3
思路
- 此题树形DP精髓：对于任意一条边，有x<y，在树中x就应该为y的父亲（因为y的约数和是唯一的，但x可能是很多个数的约数和，这正好对应树的关系，父亲唯一，孩子不定）
- dp思想是找出每个节点到叶子的最大值m1和次大值m2，再两者相加的dp[rt]，而整个树中的最大值，就是最大的dp[rt]
- m1，m2相当于分别变换到此数字之前之后的不同数的次数，感性理解
代码
#include <iostream>
#include <cstdio>
#define maxn 50005
using namespace std;
int n,sum[maxn],ans,m1[maxn],m2[maxn];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n/2;++i)
for(int j=i*2;j<=n;j+=i) sum[j]+=i;
for(int i=n;i;--i)
if(sum[i]<i)
{
if(m1[i]+1>m1[sum[i]]) m2[sum[i]]=m1[sum[i]],m1[sum[i]]=m1[i]+1;
else if(m1[i]+1>m2[sum[i]]) m2[sum[i]]=m1[i]+1;
}
for(int i=1;i<=n;++i) ans=max(ans,m1[i]+m2[i]);
printf("%d
",ans);
return 0;
}