fork download 
  1. #include <iostream> // Phan Nguyen Quoc Bao
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define task "coci2021_r1_papricice"
  5. const int N = 2e5 + 5 ; 
  6. int n ; 
  7. vector<int> D[N] ;  
  8. void Inp()
  9. {
  10.     cin >> n ; 
  11.     for(int i = 1 ; i < n ; i++){
  12.         int u , v ;
  13.         cin >> u>> v; 
  14.         D[u].push_back(v) ;
  15.         D[v].push_back(u) ; 
  16.     }
  17. }
  18. namespace SUB1{
  19.     long long cnt[N] , tin[N] , tout[N] , stt = 0;
  20.     void dfs(int u , int p) {
  21.         tin[u] = ++stt ; 
  22.         cnt[u] = 1 ; 
  23.         for(int v : D[u]){
  24.             if(v == p) continue; 
  25.             dfs(v , u) ; 
  26.             cnt[u] += cnt[v] ; 
  27.         }
  28.         tout[u] = stt ; 
  29.     }
  30.     bool Ontree(int root , int u){
  31.         return tin[root] <= tin[u] && tin[u] <= tout[root] ; 
  32.     }
  33.     int ans = 1e9;
  34.  
  35.     void Solve(){ 
  36.         dfs(1 , 0) ;
  37.         for(int i = 2 ; i < n ; i++)
  38.             for(int j = i + 1 ; j <= n  ;j++)
  39.                 {
  40.                     int u = i , v = j , ok = 0 ; 
  41.                     if(Ontree(u , v)){
  42.                         ok = 1 ;  
  43.                     }
  44.                     if(Ontree(v , u)){
  45.                         ok = 1 ; 
  46.                         swap(u , v) ; 
  47.                     }
  48.                     int vmin , vmax ; 
  49.                     if(ok){
  50.                         vmin = min(n - cnt[u],  min(cnt[v] , cnt[u] - cnt[v])) ; 
  51.                         vmax = max(n - cnt[u] , max(cnt[v] , cnt[u] - cnt[v])) ;
  52.                     }else {
  53.                         vmin = min(n - cnt[u] - cnt[v] ,min(cnt[v] , cnt[u])) ; 
  54.                         vmax = max(n - cnt[u] - cnt[v] , max(cnt[v] , cnt[u])) ; 
  55.                     }
  56.                     ans = min(ans , vmax - vmin) ; 
  57.                 }
  58.         cout << ans <<"\n" ; 
  59.     }
  60. }
  61. namespace SUB2{
  62.     set<int> A , B ; 
  63.     int cnt[N] ;
  64.     void dfs(int u , int p){
  65.         cnt[u] = 1 ; 
  66.         for(int v : D[u]){
  67.             if(v == p) continue; 
  68.             dfs(v , u) ; 
  69.             cnt[u] += cnt[v] ; 
  70.         }
  71.     } 
  72.     int get_dif(int a , int b , int c){
  73.            return max({a , b , c}) - min({a , b , c}) ;  
  74.     }
  75.     vector<int> get_result(const set<int>&A , int x){
  76.         vector<int> res ; 
  77.         auto j = A.upper_bound(x) ; 
  78.         if(j != A.end()) res.push_back(*j) ; 
  79.         if(j != A.begin()) {
  80.             --j ; 
  81.             res.push_back(*j) ; 
  82.         }
  83.         return res ; 
  84.     }
  85.     int dfs2(int u , int p){
  86.         int res = 1e9 ; 
  87.         for(auto x : get_result(A , (n + cnt[u]) / 2)){
  88.             res = min(res , get_dif(n - x , cnt[u], x - cnt[u])) ; 
  89.         }
  90.         for(auto x : get_result(B , (n - cnt[u]) / 2)){
  91.             res = min(res , get_dif(n - x - cnt[u] , x , cnt[u])) ; 
  92.         }
  93.         A.insert(cnt[u]) ; 
  94.         for(int v : D[u]){
  95.             if(v == p) continue; 
  96.             res = min(res , dfs2(v , u)) ;     
  97.         }
  98.         A.erase(cnt[u]) ; 
  99.         B.insert(cnt[u]) ; 
  100.         return res ; 
  101.     }
  102.     void Solve(){
  103.         dfs(1 , 0) ; 
  104.         cout << dfs2(1 , 0) ; 
  105.     }
  106. }
  107. void Solve()
  108. {
  109.     if(n <= 2000){
  110.         SUB1::Solve() ; 
  111.     }else SUB2::Solve() ; 
  112.  
  113. }
  114. void Out() 
  115. {
  116.  
  117. }
  118. int main()
  119. {
  120.     ios_base::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL);
  121.     if(ifstream(task".INP")){
  122.         freopen(task".INP","r",stdin) ; 
  123.         freopen(task".OUT","w",stdout) ;
  124.     }
  125.     Inp();
  126.     Solve();
  127.     Out(); 
  128.     return 0;
  129. }
  130.  
Success #stdin #stdout 0.01s 11724KB
comments (?)
stdin 
Standard input is empty
stdout 
1000000000
https://ideone.com/PR27rW
language:
C++14 (clang 8.0)
created:
1 day ago
visibility:
public

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!