D - A Wide, Wide Graph.cpp

#ifdef DEBUG
#include "debug.h"
#endif // DEBUG
#ifndef DEBUG
template <typename T>
void debug(T &x){}
#endif // DEBUG

#include <bits/stdc++.h>

using namespace std;

vector <vector <int> > adj;
vector <int> dist;

void getDist(int pos, int par){
    for(int nxt : adj[pos]){
        if(nxt == par) continue;
        dist[nxt] = dist[pos] + 1;
        getDist(nxt, pos);
    }
}

int main(){
    cin.tie(nullptr), ios::sync_with_stdio(false);
    int n;
    cin >> n;
    adj.resize(n + 1);
    for(int i = 0; i < n - 1; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dist.resize(n + 1);
    getDist(1, 0);
    int p1 = max_element(dist.begin(), dist.end()) - dist.begin();

    fill(dist.begin(), dist.end(), 0);
    getDist(p1, 0);
    int p2 = max_element(dist.begin(), dist.end()) - dist.begin();

    vector <int> maxD(dist);
    fill(dist.begin(), dist.end(), 0);
    getDist(p2, 0);
    for(int i = 0; i <= n; i++) maxD[i] = max(maxD[i], dist[i]);
    debug(maxD);

    vector <vector<int> > v(n + 1);
    for(int i = 1; i <= n; i++){
        if(adj[i].size() == 1) v[maxD[i]].push_back(i);
    }

    vector <int> ans(n + 1, n + 1);
    queue <int> q;
    fill(dist.begin(), dist.end(), 0);
    for(int i = n - 1; i >= 1; i--){
        for(int p : v[i]) q.push(p), dist[p] = 1;

        int rep = (int)q.size();
        ans[i] = ans[i + 1] - rep;
        debug(q);
        while(rep--){
            int pos = q.front();
            q.pop();
            for(int nxt : adj[pos]){
                if(!dist[nxt]) q.push(nxt), dist[nxt] = 1;
            }
        }
    }

    for(int i = 1; i <= n; i++) cout << min(ans[i], n) << " ";
}