fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5.  
  6. #define int long long
  7. #define FOR(i, a, b) for (int i = (a); i <= (b); i++)
  8. #define FORD(i, a, b) for (int i = (b); i >= (a); i --)
  9. #define REP(i, a) for (int i = 0; i < (a); ++i)
  10. #define REPD(i, a) for (int i = (a) - 1; i >= 0; --i)
  11.  
  12. #define MASK(i) (1LL << (i))
  13. #define BIT(x, i) (((x) >> (i)) & 1)
  14.  
  15.  
  16. constexpr ll LINF = (1ll << 60);
  17. constexpr int INF = (1ll << 30);
  18. constexpr int Mod = 1e9 + 7;
  19. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  20.  
  21. /*
  22.     Phu Trong from Nguyen Tat Thanh High School for gifted student
  23. */
  24.  
  25. template <class X, class Y>
  26.     bool minimize(X &x, const Y &y){
  27.         X eps = 1e-9;
  28.         if (x > y + eps) {x = y; return 1;}
  29.         return 0;
  30.     }
  31.  
  32. template <class X, class Y>
  33.     bool maximize(X &x, const Y &y){
  34.         X eps = 1e-9;
  35.         if (x + eps < y) {x = y; return 1;}
  36.         return 0;
  37.     }
  38. #define MAX                 100005
  39. int numNode;
  40. int ans[MAX];
  41. vector<int> G[MAX];
  42.  
  43. pair<int, int> dp[MAX];
  44.  
  45. void dfs(int u, int p, int length){
  46.     dp[u] = make_pair(0, 0);
  47.     int max_len[2];
  48.     max_len[0] = max_len[1] = 0;
  49.     for (int&v : G[u]) if(v ^ p){
  50.         dfs(v, u, length);
  51.         dp[u].first += dp[v].first;
  52.         if(dp[v].second > max_len[0]){
  53.             max_len[1] = max_len[0];
  54.             max_len[0] = dp[v].second;
  55.         }
  56.         else if(dp[v].second > max_len[1]){
  57.             max_len[1] = dp[v].second;
  58.         }
  59.     }
  60.     if(max_len[0] + 1 + max_len[1] >= length){
  61.         ++dp[u].first;
  62.         dp[u].second = 0;
  63.     }
  64.     else{
  65.         dp[u].second = max_len[0] + 1;
  66.     }
  67. }
  68.  
  69. void solve(int l, int r, int min_value, int max_value){
  70.     if (l > r) return;
  71.     if(min_value == max_value){
  72.         FOR(i, l, r) ans[i] = min_value;
  73.         return;
  74.     }
  75.  
  76.     int m = (l + r) >> 1;
  77.     dfs(1, 1, m);
  78.     int res = dp[1].first;
  79.     ans[m] = res;
  80.  
  81.     solve(l, m - 1, res, max_value);
  82.     solve(m + 1, r, min_value, res);
  83. }
  84. void process(void){
  85.     cin >> numNode;
  86.     for (int i = 1; i < numNode; ++i){
  87.         int u, v; cin >> u >> v;
  88.         G[u].emplace_back(v);
  89.         G[v].emplace_back(u);
  90.     }
  91.     solve(1, numNode, 0, numNode);
  92.  
  93.     for (int i = 1; i <= numNode; ++i) cout << ans[i] << '\n';
  94. }
  95. signed main(){
  96.     #define name "Whisper"
  97.     cin.tie(nullptr) -> sync_with_stdio(false);
  98.     //freopen(name".inp", "r", stdin);
  99.     //freopen(name".out", "w", stdout);
  100.     process();
  101.     return (0 ^ 0);
  102. }
  103.  
  104.  
  105.  
  106.  
  107.  
Success #stdin #stdout 0.01s 7668KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/kcAJAX
language:
C++14 (gcc 8.3)
created:
30 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!