fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define faster ios_base::sync_with_stdio(false); cin.tie(NULL)
  4. #define fi first
  5. #define se second
  6.  
  7. const int N = 1e5 + 7;
  8. int n , cnt = 0 , k;
  9. vector<int> a[N];
  10. int tin[N] , h[N] , up[21][N];
  11.  
  12. void dfs(int u , int p){
  13.     tin[u] = ++cnt;
  14.     for (int v : a[u]) if (v != p){
  15.         h[v] = h[u] + 1;
  16.         up[0][v] = u;
  17.  
  18.         dfs(v , u);
  19.     }
  20. }
  21.  
  22. void inp(){
  23.     cin >> n >> k;
  24.     for (int i = 1 ; i < n ; ++i){
  25.         int u , v;
  26.         cin >> u >> v;
  27.         ++u,++v;
  28.         a[u].push_back(v);
  29.         a[v].push_back(u);
  30.     }
  31.  
  32.     h[1] = 1;
  33.     dfs(1 , 0);
  34.  
  35.     for (int j = 1 ; j <= 20 ; ++j){
  36.         for (int i = 1 ; i <= n ; ++i){
  37.             up[j][i] = up[j - 1][up[j - 1][i]];
  38.         }
  39.     }
  40. }
  41.  
  42. int lca(int u , int v){
  43.     if (h[u] < h[v]) swap(u , v);
  44.  
  45.     for (int i = 20 ; i >= 0 ; --i) if(h[up[i][u]] >= h[v]){
  46.         u = up[i][u];
  47.     }
  48.  
  49.     if (u == v) return u;
  50.  
  51.     for (int i = 20 ; i >= 0 ; --i) if (up[i][u] != up[i][v]){
  52.         u = up[i][u];
  53.         v = up[i][v];
  54.     }
  55.  
  56.     return up[0][u];
  57. }
  58.  
  59. int d(int u , int v){
  60. //    if (u == 0 || v == 0) return 0;
  61. //    if (u == n + 1 || v == n + 1) return 0;
  62.     int p = lca(u , v);
  63.  
  64.     return h[u] + h[v] - 2 * h[p];
  65. }
  66.  
  67. int Cnt = 0;
  68. set<pair<int , int>> st;
  69.  
  70. void Push(int id , int in){
  71.     st.insert({in , id});
  72.     if (st.size() == 1) return;
  73.     auto it = st.lower_bound({in , id});
  74.     auto it2 = it;
  75.     ++it2;
  76.  
  77.     if (it == st.begin()){
  78.         auto it1 = st.rbegin();
  79.  
  80.         if (st.size() > 2) Cnt -= d(it1->se , it2->se);
  81.         Cnt += d(it->se , it2->se);
  82.         Cnt += d(it->se , it1->se);
  83.         return;
  84.     }
  85.     if (it2 == st.end()){
  86.         it2 = st.begin();
  87.         auto it1 = it;
  88.         --it1;
  89.  
  90.         if (st.size() > 2) Cnt -= d(it1->se , it2->se);
  91.         Cnt += d(it->se , it2->se);
  92.         Cnt += d(it->se , it1->se);
  93.         return;
  94.     }
  95.  
  96.     auto it1 = it;
  97.     --it1;
  98.     Cnt -= d(it1->se , it2->se);
  99.     Cnt += d(it->se , it2->se);
  100.     Cnt += d(it->se , it1->se);
  101. }
  102.  
  103. void Erase(int id , int in){
  104.     auto it = st.lower_bound({in , id});
  105.     if (st.size() == 1){
  106.         st.erase(it);
  107.         return;
  108.     }
  109.     auto it2 = it;
  110.     ++it2;
  111.  
  112.     if (it == st.begin()){
  113.         auto it1 = st.rbegin();
  114.  
  115.         if (st.size() > 2) Cnt += d(it1->se , it2->se);
  116.         Cnt -= d(it->se , it2->se);
  117.         Cnt -= d(it->se , it1->se);
  118.         st.erase(it);
  119.         return;
  120.     }
  121.     if (it2 == st.end()){
  122.         it2 = st.begin();
  123.         auto it1 = it;
  124.         --it1;
  125.  
  126.         if (st.size() > 2) Cnt += d(it1->se , it2->se);
  127.         Cnt -= d(it->se , it2->se);
  128.         Cnt -= d(it->se , it1->se);
  129.         st.erase(it);
  130.         return;
  131.     }
  132.  
  133.     auto it1 = it;
  134.     --it1;
  135.     Cnt += d(it1->se , it2->se);
  136.     Cnt -= d(it->se , it2->se);
  137.     Cnt -= d(it->se , it1->se);
  138.  
  139.     st.erase(it);
  140. }
  141.  
  142. void solve(){
  143.     int i = 1 , j = 1 , res = 1;
  144.  
  145.     Push(1  , tin[1]);
  146.     while (i <= n){
  147.         while (j < n && Cnt <= k * 2){
  148.             ++j;
  149.             Push(j , tin[j]);
  150.         }
  151.         if (Cnt > k * 2){
  152.             Erase(j , tin[j]);
  153.             --j;
  154.         }
  155.  
  156.         res = max(res , j - i + 1);
  157.         Erase(i , tin[i]);
  158.         ++i;
  159.     }
  160.  
  161.     cout << res;
  162. }
  163.  
  164. int main(){
  165. //    freopen("difmax.inp" , "r" , stdin);
  166. //    freopen("difmax.out" , "w" , stdout);
  167.     faster;
  168.     inp();
  169.     solve();
  170.     return 0;
  171. }
  172.  
Success #stdin #stdout 0s 7612KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/wzonsc
language:
C++14 (gcc 8.3)
created:
9 hours 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!