Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <cassert>
- //#include <vector>
- //#include <iostream>
- #pragma comment(linker,"/STACK:100000000")
- using namespace std;
- const int c=3000002;
- int o[c];
- int n;
- int* e[c];
- //int m[c]; // сколько вершин в этом поддереве
- int p[c]; // сколько торчит наверх
- bool b[c];
- bool q;
- int t;
- int pw[c];
- /*
- void init(int i, int k) {
- m[i]=1;
- int j;
- for (j=0; j<e[i].size(); ++j) if (e[i][j]!=k) {
- init(e[i][j],i);
- m[i]+=m[e[i][j]];
- }
- }
- */
- void go(int i, int k) {
- // if (i%1000==40) cerr << i << ' ' << k << '\n';
- assert(i>k);
- int j;
- int sp=0;
- for (j=0; j<pw[i]; ++j) if (e[i][j]!=k) {
- go(e[i][j],i);
- if (!q) return;
- sp+=p[e[i][j]];
- }
- // cerr << i << ' ' << t << ' ' << q << ' ' << sp << '\n';
- sp++;
- if (sp>t) q=0; else {
- p[i]=sp%t;
- }
- }
- int main() {
- scanf("%d",&n);
- int i,j,k;
- for (i=2; i<=n; ++i) {
- scanf("%d",&o[i]);
- //pw[i]++;
- pw[o[i]]++;
- }
- for (i=1; i<=n; ++i) if(pw[i]) {
- e[i]=(int*)malloc(sizeof(int)*pw[i]);
- // if (e[i]==0) cerr << "null\n";
- }
- // cerr << "!\n";
- memset(pw,0,sizeof(pw));
- for (i=2; i<=n; ++i) {
- //e[i][pw[i]++]=o[i];
- e[o[i]][pw[o[i]]++]=i;
- }
- // init(1,0);
- for (i=2; i<n; ++i) if (n%i==0) {
- // cerr << i << '\n';
- t=n/i;
- q=1;
- go(1,0);
- // cerr << i << '\n';
- // for (j=1; j<=n; ++j) cerr << p[j] << ' ';
- // cerr << '\n';
- if (q) b[i]=1;
- }
- b[1]=b[n]=1;
- for (i=1; i<=n; ++i) if (b[i]) printf("%d ",i);
- printf("\n");
- // cerr << sizeof(e)+sizeof(p)+sizeof(res) << '\n';
- // for (i=1; i<=n; ++i) free(e[i]);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement