fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const long long MaxN = 2e5 + 5;
  4. long long n,sz[MaxN],sum=1,cnt,k;
  5. vector<long long> a[MaxN];
  6. void dfs(long long i, long long par, long long check)
  7. {
  8.         for(long long x:a[i])
  9.         {
  10.             if(x!=par)
  11.             {
  12.                 dfs(x,i,check);
  13.                 sz[i]+=sz[x];
  14.             }
  15.         }
  16.         if (sz[i]>=check)
  17.         {
  18.             cnt++;
  19.             sz[i]=0;
  20.         }
  21.  
  22. }
  23. bool check(long long mid)
  24. {
  25.     dfs(1,1,mid);
  26.     return cnt>=k+1;
  27. }
  28. int main()
  29. {
  30.     ios_base::sync_with_stdio(0);
  31.     cin.tie(0);
  32.     cin >> n >> k;
  33.     for (long long i=1; i<=n-1; i++)
  34.     {
  35.         long long u,v;
  36.         cin >> u >> v;
  37.         a[u].push_back(v);
  38.         a[v].push_back(u);
  39.     }
  40.     long long l=1, r=n;
  41.     while (l<=r)
  42.     {
  43.         for (long long i=1; i<=n; i++)
  44.         {
  45.             sz[i]=1;
  46.         }
  47.         long long  mid=(l+r)/2;
  48.         cnt=0;
  49.         if (check(mid))
  50.         {
  51.             l=mid+1;
  52.         }
  53.         else
  54.         {
  55.             r=mid-1;
  56.         }
  57.     }
  58.     cout << r;
  59. }
Success #stdin #stdout 0.01s 9476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/z2mKOy
language:
C++14 (gcc 8.3)
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!