1056D - Decorate Apple Tree - CodeForces Solution

#include <bits/stdc++.h>

#include <random>

using namespace std;

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

#ifndef LOCAL
#pragma GCC optimize("unroll-loops,inline,Ofast")
// #pragma GCC target("avx2")
#endif

//#define int long long
//#define double long double
#define ont long long
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define pint pair<int, int>
#define endl '\n'

template<class T>
bool cmax(T& a, T b) {
    if (a >= b) return false;
    a = b;
    return true;
}

template<class T>
bool cmin(T& a, T b) {
    if (a <= b) return false;
    a = b;
    return true;
}

vector<vector<int>> graph;
vector<int> leaf;

void dfs(int v) {
    for (auto& to : graph[v]) {
        dfs(to);
        leaf[v] += leaf[to];
    }
    leaf[v] += !leaf[v];
}

inline void solve() {
    int n;
    cin >> n;
    graph.resize(n);
    leaf.resize(n);
    for (int i = 1; i < n; ++i) {
        int x;
        cin >> x;
        graph[--x].push_back(i);
    }
    dfs(0);
    vector<int> ct(n);
    for (auto& x : leaf) ct[x]++;
    int i = 0;
    int sum = 0;
    for (int k = 1; k <= n; ++k) {
        while (sum < k) i++, sum += ct[i];
        cout << i << ' ';
    }
}

signed main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int ttt = 1;
//    cin >> ttt;
    while (ttt--) {
        solve();
    }
}