题目大意：给定一棵树，要求将这棵树分成
首先的约数。(废话 然后我们有一个结论：某个的倍数 证明： 首先不可能存在超过的倍数，这是废话 首先证明必要性： 假设我们已经有了一组合法的方案，那么对于每一个连通块，我们找到这个连通块中深度最小的节点，以这个节点为根的子树大小一定是的倍数 由于这样的节点有个，因此必要性得证 下面来证明充分性： 假设现在我们已经找到了的倍数，那么： 首先我们从根节点出发开始DFS，每遇到一个节点满足以这个节点为根的子树大小是的倍数，就把这个节点为根的子树砍掉 这样做之后，，我们得到了一个连通块和一些子树，其中连通块的大小为个节点都在那些子树中 对每个子树重复这一操作，一定能得到一组合法的方案 因此充分性得证
然后就好办了，我们搞出每个节点的(这里不要DFS，会T掉)，然后令数组中扫一遍即可 时间复杂度
;int n;int divisors[2020],tot;int fa[M],size[M],f[M];void Initialize(){memset(size,0,sizeof size);memset(f,0,sizeof f);}void Decomposition(int n){int i;for(i=1;i*i<n;i++)if(n%i==0)divisors[++tot]=i,divisors[++tot]=n/i;if(i*i==n)divisors[++tot]=i;sort(divisors+1,divisors+tot+1);}namespace IStream{#define L (1<<16)char Get_Char(){static char buffer[L],*S,*T;if(S==T){T=(S=buffer)+fread(buffer,1,L,stdin);if(S==T) return EOF;}return *S++;}int Get_Int(){int re=0;char c=Get_Char();while(c<‘0’||c>’9′)c=Get_Char();while(c>=’0’&&c<=’9’)re=(re<<1)+(re<<3)+(c-‘0’),c=Get_Char();return re;}}int main(){IStream;int T,i,j;cin>>n;Decomposition(n);for(T=1;T<=10;T++){printf(“Case #%d:\n”,T);Initialize();for(i=2;i<=n;i++){if(T==1)fa[i]=Get_Int();elsefa[i]=(fa[i]+19940105)%(i-1)+1;}for(i=n;i;i–)size[fa[i]]+=++size[i];for(i=1;i<=n;i++)f[size[i]]++;for(i=1;i<=tot;i++){int temp=0;for(j=divisors[i];j<=n;j+=divisors[i])temp+=f[j];if(temp==n/divisors[i])printf(“%d\n”,divisors[i]);}}return 0;}
你怎么样对待别人被人就怎么样对待你。
