Advertisement
Guest User

Untitled

a guest
Apr 8th, 2018
365
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.77 KB | None | 0 0
  1. #include <cmath>
  2. #include <iostream>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <string>
  6. #include <set>
  7. #include <map>
  8. #include <list>
  9. #include <time.h>
  10. #include <math.h>
  11. #include <random>
  12. #include <deque>
  13. #include <queue>
  14. #include <cassert>
  15. #include <unordered_map>
  16. #include <iomanip>
  17. #include <bitset>
  18.  
  19. using namespace std;
  20.  
  21. typedef long long ll;
  22.  
  23. mt19937 rnd(228);
  24.  
  25. const int N = 2e5 + 7;
  26.  
  27. vector <int> g[N];
  28. int sz[N];
  29. int ans[N];
  30. int t[4 * N];
  31. int d[4 * N];
  32.  
  33. void push(int v)
  34. {
  35.     d[v * 2 + 1] += d[v];
  36.     d[v * 2 + 2] += d[v];
  37.     t[v * 2 + 1] += d[v];
  38.     t[v * 2 + 2] += d[v];
  39.     d[v] = 0;
  40. }
  41.  
  42. void upd(int v, int l, int r, int tl, int tr, int x)
  43. {
  44.     if (tl >= r || tr <= l)
  45.     {
  46.         return;
  47.     }
  48.     if (tl >= l && tr <= r)
  49.     {
  50.         t[v] += x;
  51.         d[v] += x;
  52.     }
  53.     else
  54.     {
  55.         int tm = (tl + tr) / 2;
  56.         push(v);
  57.         upd(v * 2 + 1, l, r, tl, tm, x);
  58.         upd(v * 2 + 2, l, r, tm, tr, x);
  59.         t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
  60.     }
  61. }
  62.  
  63. void dfs(int v, int pr)
  64. {
  65.     sz[v] = 1;
  66.     for (int to : g[v])
  67.     {
  68.         if (to != pr)
  69.         {
  70.             dfs(to, v);
  71.             sz[v] += sz[to];
  72.         }
  73.     }
  74. }
  75.  
  76. int n;
  77.  
  78. void relax()
  79. {
  80.     while (t[0] >= 0)
  81.     {
  82.         int v = 0;
  83.         int l = 0, r = N;
  84.         while (l < r - 1)
  85.         {
  86.             int m = (l + r) / 2;
  87.             push(v);
  88.             if (t[v * 2 + 1] >= 0)
  89.             {
  90.                 r = m;
  91.                 v = v * 2 + 1;
  92.             }
  93.             else
  94.             {
  95.                 l = m;
  96.                 v = v * 2 + 2;
  97.             }
  98.         }
  99.         ans[l]++;
  100.         upd(0, l, r, 0, N, -t[v] - l);
  101.     }
  102. }
  103.  
  104. int get(int v, int l, int r, int i)
  105. {
  106.     if (r - l == 1)
  107.     {
  108.         return t[v];
  109.     }
  110.     else
  111.     {
  112.         int m = (l + r) / 2;
  113.         push(v);
  114.         if (i < m)
  115.         {
  116.             return get(v * 2 + 1, l, m, i);
  117.         }
  118.         else
  119.         {
  120.             return get(v * 2 + 2, m, r, i);
  121.         }
  122.     }
  123. }
  124.  
  125. void solve(int v, int pr)
  126. {
  127.     int x = -1;
  128.     for (int to : g[v])
  129.     {
  130.         if (to != pr)
  131.         {
  132.             if (x == -1 || sz[to] > sz[x])
  133.             {
  134.                 x = to;
  135.             }
  136.         }
  137.     }
  138.     vector <int> know;
  139.     for (int to : g[v])
  140.     {
  141.         if (to != pr && to != x)
  142.         {
  143.             solve(to, v);
  144.             while ((int) know.size() <= sz[to])
  145.             {
  146.                 know.push_back(0);
  147.             }
  148.             for (int x = 1; x <= sz[to]; x++)
  149.             {
  150.                 int val = get(0, 0, N, x);
  151.                 know[x] += val + x;
  152.                 upd(0, x, x + 1, 0, N, -val - x);
  153.             }
  154.         }
  155.     }
  156.     for (int to : g[v])
  157.     {
  158.         if (to != pr && to == x)
  159.         {
  160.             solve(to, v);
  161.         }
  162.     }
  163.     for (int to : g[v])
  164.     {
  165.         if (to != pr)
  166.         {
  167.             upd(0, sz[to] + 1, sz[v] + 1, 0, N, sz[to]);
  168.         }
  169.     }
  170.     upd(0, 0, sz[v] + 1, 0, N, 1);
  171.     for (int i = 1; i < (int) know.size(); i++)
  172.     {
  173.         upd(0, i, i + 1, 0, N, know[i]);
  174.     }
  175.     relax();
  176. }
  177.  
  178. int main()
  179. {
  180. #ifdef ONPC
  181.     freopen("a.in", "r", stdin);
  182. #endif
  183.     ios::sync_with_stdio(0);
  184.     cin.tie(0);
  185.     cin >> n;
  186.     for (int i = 1; i < n; i++)
  187.     {
  188.         int a, b;
  189.         cin >> a >> b;
  190.         a--, b--;
  191.         g[a].push_back(b);
  192.         g[b].push_back(a);
  193.     }
  194.     for (int i = 0; i < N; i++)
  195.     {
  196.         if (1 <= i && i <= n)
  197.         {
  198.             upd(0, i, i + 1, 0, N, -i);
  199.         }
  200.         else
  201.         {
  202.             upd(0, i, i + 1, 0, N, -N);
  203.         }
  204.     }
  205.     dfs(0, -1);
  206.     solve(0, -1);
  207.     for (int i = 1; i <= n; i++)
  208.     {
  209.         cout << ans[i] << '\n';
  210.     }
  211. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement