挺巧妙的一道题，类似树形DP
大致题意：
先给你一棵树，然后会让你改变9次树的形态，问：对于原始状态和每次改变后的这棵树，要你把这棵树的节点分成若干组，使得所有组的节点均相连且所有组的节点数相同。请问当每组的节点数均为多少的满足条件。
可以发现，每组的节点数一定是n的约数，且1，n肯定是。然后，通过画图等大力分析枚举后，可以得到一个性质：若存在一个答案x，那么此刻树中的所有子节点的子树大小是x的倍数的子树个数，一定>=n/x。（好多题解都是>=n/x，但是我感觉好像不会有>的情况的，只能等于，用等于试了一下是对的。）——————性质1
那么现在我们要求每个节点的子树大小了，dfs当然可以，虽然是O(n),不过常数挺大，现在又有一个性质：对于(f[x]+19940105)mod(x-1)+1，我们发现，x的父节点，一定比x小，所以，倒着O(n)更新一遍节点子树大小即可。————性质2
两个性质，都是看题解的…
#include
using namespace std;
const int N=1200005;
int n,cnt;
int fa[N],size[N],sum[N],num[N],prime[N];int main(){scanf("%d",&n);fa[1]=1;for (register int i=2; i<n; ++i) scanf("%d,",&fa[i]);scanf("%d",&fa[n]);for (register int i=2; i<n; ++i) if (n%i==0) prime[++cnt]=i;for (register int t=1; t<=10; ++t){memset(size,0,sizeof(size));memset(sum,0,sizeof(sum));memset(num,0,sizeof(num));if (t!=1) for (register int i=2; i<=n; ++i) fa[i]=(fa[i]+19940105)%(i-1)+1;for (register int i=1; i<=n; ++i) size[i]=1;for (register int i=n; i>1; --i) size[fa[i]]+=size[i];for (register int i=1; i<=n; ++i) num[size[i]]++;printf("Case #%d:\n",t);printf("%d\n",1);for (register int i=1; i<=cnt; ++i){int now=0;for (register int j=1; j*prime[i]<=n; ++j) now+=num[j*prime[i]];if (now*prime[i]>=n) printf("%d\n",prime[i]);}printf("%d\n",n);}
return 0;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！
