1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #define endl "\n"
  5. #define quick ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  6. #define ALL(x) x.begin(),x.end()
  7. #define SORT(x) sort(ALL(x))
  8. #define FOR(a,b,c) for(ll (a)= (b);(a)<(c);++(a))
  9. #define REP(a,b) FOR(a,0,b)
  10. #define mp make_pair
  11. #define pb push_back
  12. #define pll pair<ll,ll>
  13. #define pii pair<int,int>
  14. #define vl vector<ll>
  15. #define vi vector<int>
  16. #define f first
  17. #define s second
  18. #define yy cout<<"YES"<<endl;return
  19. #define nn cout<<"NO"<<endl;return
  20. #define minus1 cout<<-1<<endl;return
  21. #define rd(a,x) REP(i,x)cin >> a[i]
  22. int ttt = 1, case_ = 0;
  23. ll n, m, k;
  24. vector<vl> G;
  25. vl p;
  26. vl d;
  27. vl b;
  28. template <class myType>
  29. void print_arr(myType &arr, ll L, string sep){
  30. REP(i,L){ cout << arr[i] << (i < L-1 ? sep : "\n"); }
  31. return; }
  32. /*
  33. */
  34. void dfs(ll u) {
  35. for(ll v: G[u]) {
  36. if (v == p[u]) continue;
  37. dfs(v);
  38. if (d[u] < d[v] + 1) {
  39. b[u] = v;
  40. d[u] = d[v] + 1;
  41. }
  42. }
  43. return;
  44. }
  45. void solve() {
  46. cin >> n;
  47. G.resize(n);
  48. p.resize(n);
  49. d.resize(n);
  50. b.resize(n);
  51. vector<bool> used(n, 0);
  52. REP(i, n) {
  53. d[i] = 0;
  54. b[i] = -1;
  55. G[i].clear();
  56. }
  57. p[0] = -1;
  58. FOR(i, 1, n) {
  59. cin >> p[i];
  60. p[i]--;
  61. G[i].pb(p[i]);
  62. G[p[i]].pb(i);
  63. }
  64. dfs(0);
  65. priority_queue<pll> q;
  66. REP(i, n) {
  67. q.push(mp(d[i], i));
  68. }
  69. vl ans;
  70. ll curr = 0;
  71. REP(i, n) {
  72. while (!q.empty() && used[q.top().s]) {
  73. q.pop();
  74. }
  75. if (q.empty()) {
  76. ans.pb(n);
  77. continue;
  78. }
  79. auto [depth, node] = q.top();
  80. q.pop();
  81. curr += depth + 1;
  82. used[node] = 1;
  83. while (b[node] != -1) {
  84. node = b[node];
  85. used[node] = 1;
  86. }
  87. ans.pb(curr);
  88. }
  89. print_arr(ans, n, " ");
  90. return;
  91. }
  92. int main() {
  93. quick;
  94. //cin >> ttt;
  95. while (ttt--) solve();
  96. return 0;
  97. }
Comments powered by Disqus