fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define all(v) v.begin() , v.end()
  5. #define sz(v) int(v.size())
  6. #define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
  7. using namespace std;
  8.  
  9. typedef long long ll;
  10. typedef pair<int , int> ii;
  11. typedef pair<long long , int> lli;
  12.  
  13. const int maxN = int(2e5)+7;
  14. const int inf = int(1e9)+7;
  15.  
  16. int n;
  17. vector<int> g[maxN];
  18. int dp[maxN];
  19. bool bad;
  20.  
  21. void dfs(int u , int par , int k){
  22.     dp[u] = 0;
  23.     for (int v : g[u]){
  24.         if (v != par){
  25.             if (bad) return;
  26.             dfs(v , u , k);
  27.         }
  28.     }
  29.     multiset<int> st;
  30.     for (int v : g[u]){
  31.         if (v != par){
  32.             st.insert(dp[v] + 1);
  33.         }
  34.     }
  35.     if (st.empty()) return;
  36.     while (sz(st) > 2){
  37.         int x = *st.begin(); st.erase(st.begin());
  38.         if (st.lower_bound(k - x) == st.end()){
  39.             dp[u] = x;
  40.             while (st.empty() == 0){
  41.                 int y = *st.begin();
  42.                 if (y >= k) continue;
  43.                 auto it = st.lower_bound(k - y);
  44.                 if (it == st.end()){
  45.                     bad = true;
  46.                     return;
  47.                 }
  48.                 st.erase(it);
  49.             }
  50.             return;
  51.         }
  52.         st.erase(st.lower_bound(k - x));
  53.     }
  54.     if (sz(st) == 1){
  55.         dp[u] = *st.begin();
  56.     }
  57.     else{
  58.         int x = *st.begin(); st.erase(st.begin());
  59.         int y = *st.begin(); st.erase(st.begin());
  60.         if (x + y < k){
  61.             bad = true;
  62.             return;
  63.         }
  64.         if (y >= k){
  65.             dp[u] = x;
  66.         }
  67.         else{
  68.             dp[u] = 0;
  69.         }
  70.     }
  71. }
  72.  
  73. bool check(int k){
  74.     bad = false;
  75.     multiset<int> st;
  76.     for (int v : g[1]){
  77.         dfs(v , 1 , k);
  78.         st.insert(dp[v] + 1);
  79.     }
  80.     if (bad){
  81.         return false;
  82.     }
  83.     else{
  84.         while (st.empty() == 0){
  85.             int x = *st.begin(); st.erase(st.begin());
  86.             if (x >= k) continue;
  87.             auto it = st.lower_bound(k - x);
  88.             if (it == st.end()) return false;
  89.             st.erase(it);
  90.         }
  91.         return true;
  92.     }
  93. }
  94.  
  95. void solve(){
  96.     cin >> n;
  97.     for (int i = 1 ; i < n ; i++){
  98.         int u , v;
  99.         cin >> u >> v;
  100.         g[u].push_back(v);
  101.         g[v].push_back(u);
  102.     }
  103.     int lef = 0 , rig = n - 1 , ans = -1;
  104.     while (lef <= rig){
  105.         int mid = (lef + rig) / 2;
  106.         if (check(mid)){
  107.             ans = mid;
  108.             lef = mid + 1;
  109.         }
  110.         else{
  111.             rig = mid - 1;
  112.         }
  113.     }
  114.     cout << ans << "\n";
  115. }
  116.  
  117. #define name "P"
  118.  
  119. int main(){
  120.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  121.     if (fopen(name".INP" , "r")){
  122.         freopen(name".INP" , "r" , stdin);
  123.         freopen(name".OUT" , "w" , stdout);
  124.     }
  125.     int t = 1; //cin >> t;
  126.     while (t--) solve();
  127.     return 0;
  128. }
  129.  
  130.  
Success #stdin #stdout 0.01s 8336KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/ILuyKU
language:
C++ (gcc 8.3)
created:
5 days 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!