Advertisement
Guest User

Untitled

a guest
Nov 13th, 2011
191
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.63 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <cassert>
  5. //#include <vector>
  6. //#include <iostream>
  7. #pragma comment(linker,"/STACK:100000000")
  8. using namespace std;
  9. const int c=3000002;
  10. int o[c];
  11. int n;
  12. int* e[c];
  13. //int m[c]; // сколько вершин в этом поддереве
  14. int p[c]; // сколько торчит наверх
  15. bool b[c];
  16. bool q;
  17. int t;
  18. int pw[c];
  19. /*
  20. void init(int i, int k) {
  21.     m[i]=1;
  22.     int j;
  23.     for (j=0; j<e[i].size(); ++j) if (e[i][j]!=k) {
  24.         init(e[i][j],i);
  25.         m[i]+=m[e[i][j]];
  26.     }
  27. }
  28. */
  29. void go(int i, int k) {
  30. //  if (i%1000==40) cerr << i << ' ' << k << '\n';
  31.     assert(i>k);
  32.     int j;
  33.     int sp=0;
  34.     for (j=0; j<pw[i]; ++j) if (e[i][j]!=k) {
  35.         go(e[i][j],i);
  36.         if (!q) return;
  37.         sp+=p[e[i][j]];
  38.     }
  39. //  cerr << i << ' ' << t << ' ' << q << ' ' << sp << '\n';
  40.     sp++;
  41.     if (sp>t) q=0; else {
  42.         p[i]=sp%t;
  43.     }
  44. }
  45. int main() {
  46.     scanf("%d",&n);
  47.     int i,j,k;
  48.     for (i=2; i<=n; ++i) {
  49.         scanf("%d",&o[i]);
  50.         //pw[i]++;
  51.         pw[o[i]]++;
  52.     }
  53.     for (i=1; i<=n; ++i) if(pw[i]) {
  54.         e[i]=(int*)malloc(sizeof(int)*pw[i]);
  55. //      if (e[i]==0) cerr << "null\n";
  56.     }
  57. //  cerr << "!\n";
  58.     memset(pw,0,sizeof(pw));
  59.     for (i=2; i<=n; ++i) {
  60.         //e[i][pw[i]++]=o[i];
  61.         e[o[i]][pw[o[i]]++]=i;
  62.     }
  63. //  init(1,0);
  64.     for (i=2; i<n; ++i) if (n%i==0) {
  65. //      cerr << i << '\n';
  66.         t=n/i;
  67.         q=1;
  68.         go(1,0);
  69. //      cerr << i << '\n';
  70. //      for (j=1; j<=n; ++j) cerr << p[j] << ' ';
  71. //      cerr << '\n';
  72.         if (q) b[i]=1;
  73.     }
  74.     b[1]=b[n]=1;
  75.     for (i=1; i<=n; ++i) if (b[i]) printf("%d ",i);
  76.     printf("\n");
  77. //  cerr << sizeof(e)+sizeof(p)+sizeof(res)  << '\n';
  78. //  for (i=1; i<=n; ++i) free(e[i]);
  79.     return 0;
  80. }
  81.  
  82.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement