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;
29. template <class myType>
30. void print_arr(myType &arr, ll L, string sep){
31. REP(i,L){ cout << arr[i] << (i < L-1 ? sep : "\n"); }
32. return; }
34. /*
36. */
38. void dfs(ll u) {
39. for(ll v: G[u]) {
40. if (v == p[u]) continue;
41. dfs(v);
42. if (d[u] < d[v] + 1) {
43. b[u] = v;
44. d[u] = d[v] + 1;
45. }
46. }
47. return;
48. }
50. void solve() {
51. cin >> n;
52. G.resize(n);
53. p.resize(n);
54. d.resize(n);
55. b.resize(n);
56. vector<bool> used(n, 0);
57. REP(i, n) {
58. d[i] = 0;
59. b[i] = -1;
60. G[i].clear();
61. }
62. p[0] = -1;
63. FOR(i, 1, n) {
64. cin >> p[i];
65. p[i]--;
66. G[i].pb(p[i]);
67. G[p[i]].pb(i);
68. }
69. dfs(0);
70. priority_queue<pll> q;
71. REP(i, n) {
72. q.push(mp(d[i], i));
73. }
74. vl ans;
75. ll curr = 0;
76. REP(i, n) {
77. while (!q.empty() && used[q.top().s]) {
78. q.pop();
79. }
80. if (q.empty()) {
81. ans.pb(n);
82. continue;
83. }
84. auto [depth, node] = q.top();
85. q.pop();
86. curr += depth + 1;
87. used[node] = 1;
88. while (b[node] != -1) {
89. node = b[node];
90. used[node] = 1;
91. }
92. ans.pb(curr);
93. }
94. print_arr(ans, n, " ");
95. return;
96. }
98. int main() {
99. quick;
100. //cin >> ttt;
101. while (ttt--) solve();
102. return 0;
103. }

Comments powered by Disqus