Advertisement
Guest User

Untitled

a guest
Aug 20th, 2018
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.66 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define forr(i, a, b) for(int i=(int)(a);i<(int)(b);i++)
  4. #define forn(i,n) forr(i,0,n)
  5. #define dforn(i,n) for(int i=(int)(n-1);i>=0;i--)
  6. #define forall(it, v) for(auto it=v.begin();it!=v.end();it++)
  7. #define pb push_back
  8. typedef long long ll;
  9. const int MAXN=3000050;
  10.  
  11. int n,f[MAXN];
  12. vector<int> G[MAXN];
  13. vector<pair<int,int>> st,topsort;
  14. bool used[MAXN];
  15.  
  16. void getTopsort(){
  17.     st.pb(make_pair(0,-1));
  18.     while(!st.empty()){
  19.         int v=st.back().first;
  20.         int p=st.back().second;
  21.         topsort.pb(st.back());
  22.         st.pop_back();
  23.         forn(i,G[v].size()){
  24.             int w=G[v][i];
  25.             if(w==p) continue;
  26.             st.pb(make_pair(w,v));
  27.         }
  28.     }
  29.     reverse(topsort.begin(),topsort.end());
  30. }
  31.  
  32. bool check(int k){
  33.     forn(i,topsort.size()){
  34.         int v=topsort[i].first;
  35.         int p=topsort[i].second;
  36.         f[v]=1;
  37.         forn(j,G[v].size()){
  38.             int w=G[v][j];
  39.             if(w==p) continue;
  40.             f[v]+=f[w];
  41.         }
  42.         if(f[v]>k) return false;
  43.         if(f[v]==k) f[v]=0;
  44.     }
  45.     return true;
  46. }
  47.  
  48. int main() {
  49.     //~ freopen("L.in", "r", stdin);
  50.     if(scanf("%d",&n)>=1){
  51.         forn(i,n-1){
  52.             int p;scanf("%d",&p);--p;
  53.             G[i+1].pb(p);
  54.             G[p].pb(i+1);
  55.         }
  56.         getTopsort();
  57.         //~ puts("TOPSORT:");
  58.         //~ forn(i,topsort.size()){
  59.             //~ printf("%d ",topsort[i].first+1);
  60.         //~ }
  61.         //~ puts("");
  62.         vector<int> ans;
  63.         for(ll d=1;d*d<=n;d++){
  64.             if(n%d==0){
  65.                 if(d*d==n){
  66.                     if(check(d)){
  67.                         ans.pb(d);
  68.                     }
  69.                 } else {
  70.                     if(check(d)){
  71.                         ans.pb(n/d);
  72.                     }
  73.                     if(check(n/d)){
  74.                         ans.pb(d);
  75.                     }
  76.                 }
  77.             }
  78.         }
  79.         sort(ans.begin(),ans.end());
  80.         forn(i,ans.size()){
  81.             if(i)printf(" ");
  82.             printf("%d",ans[i]);
  83.         }
  84.         puts("");
  85.     }
  86.     return 0;
  87. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement