zipdang04

pastebin

Aug 2nd, 2021
867
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. /*
  4. #include <ext/pb_ds/assoc_container.hpp>
  5. #include <ext/pb_ds/tree_policy.hpp>
  6. using namespace __gnu_pbds;
  7. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
  8. */
  9.  
  10. typedef long long ll;
  11. typedef long double ld;
  12. typedef vector<int> vi;
  13. typedef vector<ll> vl;
  14. typedef pair<int, int> pii;
  15. typedef pair<ll, ll> pll;
  16. typedef map<int, int> mii;
  17. typedef unordered_map<int, int> umii;
  18. typedef map<ll, ll> mll;
  19. typedef unordered_map<ll, ll> umll;
  20. template <class T1, class T2>
  21. void maximize(T1 &a, T2 b){
  22.     if (b > a) a = b;
  23. }
  24. template <class T1, class T2>
  25. void minimize(T1 &a, T2 b){
  26.     if (b < a) a = b;
  27. }
  28. template <class T>
  29. void read(T &number)
  30. {
  31.     bool negative = false;
  32.     register int c;
  33.     number = 0;
  34.     c = getchar();
  35.     if (c=='-'){
  36.         negative = true;
  37.         c = getchar();
  38.     }
  39.     for (; (c>47 && c<58); c=getchar())
  40.         number = number *10 + c - 48;
  41.     if (negative)
  42.         number *= -1;
  43. }
  44. template <class T, class ...Ts>
  45. void read(T &a, Ts& ... args){
  46.     read(a);
  47.     read(args...);
  48. }
  49.  
  50. /*
  51. struct Node
  52. {
  53.     int node, len;
  54.     Node() {node = len = 0;}
  55.     Node(int node, int len) {this -> node = node, this -> len = len;}
  56. };
  57. typedef vector<Node> vg;
  58. */
  59.  
  60. #define MAX 1000001
  61. #define MOD 1000000007
  62.  
  63. #define fi first
  64. #define se second
  65. #define pf push_front
  66. #define pb push_back
  67.  
  68. #define FOR(type, i, a, b) for(type i = (a); i <= (b); i++)
  69. #define FORD(type, i, b, a) for(type i = (b); i >= (a); i--)
  70.  
  71. #define testBit(n, bit) ((n >> bit) & 1)
  72. #define flipBit(n, bit) (n ^ (1ll << bit))
  73. #define cntBit(n) __builtin_popcount(n)
  74. #define cntBitll(n) __builtin_popcountll(n)
  75. #define randomize mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
  76.  
  77. int n;
  78. vector<int> graph[MAX];
  79.  
  80. const int root = 1;
  81.  
  82. int cntCh[MAX];
  83. void dfs(int node, int parent){
  84.     cntCh[node] = 1;
  85.     for (int child: graph[node])
  86.         if (child != parent){
  87.             dfs(child, node);
  88.             cntCh[node] += cntCh[child];
  89.         }
  90. }
  91.  
  92. int oo = 1e9;
  93.  
  94. set<int> num[MAX];
  95.  
  96. int diff(int a, int b, int c){
  97.     if (a > b) swap(a, b);
  98.     if (a > c) swap(a, c);
  99.     if (b > c) swap(b, c);
  100.     return c - a;
  101. }
  102.  
  103. int cal(int node, int fixed){
  104.     int remain = n - fixed;
  105.     int need = (remain >> 1);
  106.    
  107.     auto it = lower_bound(num[node].begin(), num[node].end(), need);
  108.     int cur = *it;
  109.     int ans = diff(fixed, cur, remain - cur);
  110.  
  111.     if (it != num[node].begin()){
  112.         it--;
  113.         cur = *it;
  114.         minimize(ans, diff(fixed, cur, remain - cur));
  115.     }
  116.     return ans;
  117. }
  118.  
  119. int answer = oo;
  120. void haha(int node, int parent){
  121.     int bigChild = 0;
  122.  
  123.     for (int child: graph[node])
  124.         if (child != parent){
  125.             haha(child, node);
  126.  
  127.             if (cntCh[child] > cntCh[bigChild])
  128.                 bigChild = child;
  129.             if (cntCh[child] == 1) continue;
  130.  
  131.             minimize(answer, cal(child, n - cntCh[child]));
  132.         }
  133.     if (!bigChild) return;
  134.  
  135.     swap(num[node], num[bigChild]);
  136.     for (int child: graph[node])
  137.         if (child != parent && child != bigChild){
  138.             for (int x: num[child])
  139.                 minimize(answer, cal(node, x));
  140.  
  141.             num[node].insert(num[child].begin(), num[child].end());
  142.         }
  143.     num[node].insert(cntCh[node]);
  144. }
  145.  
  146. main()
  147. {
  148.     ios_base::sync_with_stdio(0); cin.tie(0);
  149.     cin >> n;
  150.     FOR(int, i, 1, n - 1){
  151.         int u, v; cin >> u >> v;
  152.         graph[u].push_back(v);
  153.         graph[v].push_back(u);
  154.     }
  155.  
  156.     dfs(1, 1);
  157.     // FOR(int, i, 1, n) cerr << cntCh[i] << " \n"[i == n];
  158.     haha(1, 1);
  159.     cout << answer << '\n';
  160. }
RAW Paste Data