考察:树形dp+约数
思路:
预处理约数之和,用倍数法,时间复杂度10^6次方左右,sum[i]<i的建立边.通过打表可知是不止一棵树,也就是数字建立的图是森林.对于遍历过的点标记一下,没标记的遍历即可.最后就是求树的直径.
倍数法中:j枚举了i的倍数
1 #include <iostream> 2 #include <algorithm> 3 #include <cstdio> 4 #include <cstring> 5 #include <vector> 6 using namespace std; 7 const int N = 50010; 8 int sum[N],f[N],ans,h[N],idx; 9 bool st[N]; 10 struct Road{ 11 int to,ne; 12 }road[N<<1]; 13 void GetDivide(int n) 14 { 15 for(int i=1;i<=n;i++) 16 for(int j=2;j<=n/i;j++)//当j=1,i=n时,sum+=n 17 sum[i*j]+=i; 18 } 19 void add(int a,int b) 20 { 21 road[idx].to = b,road[idx].ne = h[a],h[a] = idx++; 22 } 23 int dfs(int u,int fa) 24 { 25 int d1 =0,d2 = 0; 26 st[u] = 1; 27 for(int i=h[u];i!=-1;i=road[i].ne) 28 { 29 int v = road[i].to; 30 if(v==fa) continue; 31 int dist = dfs(v,u); 32 if(dist>=d1) d2 = d1,d1 = dist; 33 else if(dist>d2) d2 = dist; 34 } 35 f[u] = d1+d2; 36 } 37 int main() 38 { 39 int n; 40 scanf("%d",&n); 41 memset(h,-1,sizeof h); 42 GetDivide(n); 43 for(int i=1;i<=n;i++) 44 if(sum[i]<i) add(sum[i],i),add(i,sum[i]); 45 for(int i=1;i<=n;i++) 46 if(!st[i]) dfs(i,-1); 47 for(int i=1;i<=n;i++) ans = max(ans,f[i]); 48 printf("%d\n",ans); 49 return 0; 50 }