fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define FORU(i, a, b) for(int i = (a), _b = (b); i <= _b; i++)
  3. #define FORD(i, a, b) for(int i = (a), _b = (b); i >= _b; i--)
  4. #define MASK(x) (1LL << (x))
  5. #define BIT(x, i) (((x) >> (i)) & 1)
  6. #define ALLONE(x) (MASK(x) - 1)
  7. #define ALL(v) (v).size()
  8. #define SZ(v) (int)(v).size()
  9. #define ll long long
  10. #define fi first
  11. #define se second
  12. #define TASK "COUNTRY"
  13. #define NMAX 200005
  14. #define INF 1000000007
  15. using namespace std;
  16.  
  17. int N, K, used[NMAX];
  18. pair<int, int> dp[NMAX];
  19. vector<int> adj[NMAX];
  20.  
  21. void dfs(int u, int p, int LIM) {
  22.         used[u] = false;
  23.  
  24.         vector<int> chd;
  25.         for(int v : adj[u]) if(v != p) {
  26.                 dfs(v, u, LIM);
  27.                 chd.push_back(v);
  28.         }
  29.  
  30.         if(chd.empty()) {
  31.                 dp[u] = make_pair(0, 0);
  32.                 return;
  33.         }
  34.  
  35.         int need = 0, base = INF;
  36.         for(int v : chd)
  37.                 if(dp[v].fi == 0) need = max(need, dp[v].se + 1);
  38.                 else base = min(base, dp[v].se + 1);
  39.  
  40.         if(need + base <= LIM) dp[u] = make_pair(1, base);
  41.         else {
  42.                 dp[u] = make_pair(0, need);
  43.                 if(need == LIM) {
  44.                         used[u] = true;
  45.                         dp[u] = make_pair(1, 0);
  46.                 }
  47.         }
  48. }
  49.  
  50. bool chk(int LIM) {
  51.         dfs(1, 0, LIM);
  52.  
  53.         if(dp[1].fi == 0) used[1] = true;
  54.         int cnt = 0;
  55.         FORU(i, 1, N) cnt += used[i];
  56.  
  57.         return cnt <= K;
  58. }
  59.  
  60. int main(void) {
  61.         ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  62.         if(fopen(TASK".inp", "r")) {
  63.                 freopen(TASK".inp", "r", stdin);
  64.                 freopen(TASK".out", "w", stdout);
  65.         }
  66.  
  67.         cin >> N >> K;
  68.         FORU(i, 1, N - 1) {
  69.                 int u, v; cin >> u >> v;
  70.                 adj[u].push_back(v);
  71.                 adj[v].push_back(u);
  72.         }
  73.  
  74.         int lo = 1, hi = N - 1, res;
  75.         while(lo <= hi) {
  76.                 int mid = (lo + hi) / 2;
  77.                 if(chk(mid)) {
  78.                         res = mid;
  79.                         hi = mid - 1;
  80.                 }
  81.                 else lo = mid + 1;
  82.         }
  83.  
  84.         cout << res;
  85. }
  86.  
Success #stdin #stdout 0.01s 8560KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/V4LjLb
language:
C++ (gcc 8.3)
created:
2 years 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!