Advertisement
Guest User

Untitled

a guest
Nov 13th, 2011
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.08 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdio>
  4. #include <algorithm>
  5. using namespace std;
  6. #define pb push_back
  7. const int N = 3000005;
  8. bool cn[N];
  9. vector <int> g[N], ans;
  10. int n, x, k, p, kol, size[N];
  11. void can(int v)
  12. {
  13.   int ws;
  14.   for (int i = 0; i < g[v].size(); i++)
  15.     if (g[v][i] != p)
  16.     {
  17.       ws = p;
  18.       p = v;
  19.       can(g[v][i]);
  20.       p = ws;
  21.       size[v] += size[g[v][i]];
  22.     }
  23.   size[v]++;
  24.   if (size[v] == n / k)
  25.   {
  26.     size[v] = 0;
  27.     kol++;
  28.   }
  29. }
  30.  
  31. int main()
  32. {
  33.   cin >> n;
  34.   for (int i = 1; i < n; i++)
  35.   {
  36.     scanf("%d", &x);
  37.     --x;
  38.     g[x].pb(i);
  39.     g[i].pb(x);
  40.   }
  41.   int i;
  42.   for (i = 1; i * i <= n; i++)
  43.     if (n % i == 0)
  44.     {
  45.       for (int j = 0; j < n; j++) size[j] = 0;
  46.       kol = 0;
  47.       k = i;
  48.       p = -1;
  49.       can(0);
  50.       if (kol == i) cn[i] = true;
  51.  
  52.       for (int j = 0; j < n; j++) size[j] = 0;
  53.       kol = 0;
  54.       k = n / i ;
  55.       p = -1;
  56.       can(0);
  57.       if (kol == n / i) cn[n / i] = true;
  58.     }
  59.   for (int i = 1; i <= n; i++)
  60.     if (cn[i]) printf("%d ", i);
  61.   return 0;
  62. }
  63.  
  64.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement