fork download
copy 
  1. //******************************** JAI SAI RAM ****************************************//
  2. //help me in codeforces round 635 div2
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5. typedef long long int ll;
  6. #define endl "\n"
  7. const int sizes=400001,block=700;
  8.  
  9. ll P=1000000007;
  10. ll MAX=10000*P;
  11. ll MIN=-1*MAX;
  12.     vector<ll> adj[100001];
  13.     ll parent[100001];
  14.     ll vis[100001];
  15.     ll counts[100001];
  16.     vector<ll> levels[sizes];
  17.  
  18. void count_nodes(ll src,ll e)
  19.     {
  20.         counts[src]=1;
  21.         for(ll i=0;i<adj[src].size();i++)
  22.         {
  23.             ll v=adj[src][i];
  24.             if(v==e)
  25.             {
  26.                 continue;
  27.             }
  28.             count_nodes(v,src);
  29.            counts[src]+=counts[v];
  30.         }
  31.     }
  32.  
  33.   void dfs(ll src,ll level)
  34.   {
  35.     vis[src]=1;
  36.     levels[level].push_back(src);
  37.     for(ll i=0;i<adj[src].size();i++)
  38.     {
  39.         if(!vis[adj[src][i]])
  40.         {
  41.             parent[adj[src][i]]=src; 
  42.             dfs(adj[src][i],level+1);
  43.         }
  44.     }
  45.   }
  46. int main()
  47. {
  48.     ios_base::sync_with_stdio(false);
  49.     cin.tie(0);
  50.     ll t,n,i,j,k,l,m,o,p,q,r,s,a[sizes];
  51.     //cin>>t;
  52.     t=1;
  53.     while(t--)
  54.     {
  55.     string ss;
  56.     vector<ll> v;
  57.     //ll ans=0;
  58.     ll kk;
  59.     cin>>n>>kk;
  60.     memset(counts,0,sizeof(ll)*(n+1));
  61.     memset(vis,0,sizeof(ll)*(n+1));
  62.     memset(parent,0,sizeof(ll)*(n+1));
  63.     for(i=1;i<=n;i++)
  64.     {
  65.         levels[i].clear();
  66.         adj[i].clear();
  67.     }
  68.     for(i=0;i<n-1;i++)
  69.     {
  70.         cin>>j>>k;
  71.         adj[j].push_back(k);
  72.         adj[k].push_back(j);
  73.     }
  74.  
  75.     count_nodes(1,0);
  76.     dfs(1,1);
  77.     ll ans=0;
  78.     l=0;
  79.   k=kk;
  80.     vector<ll> se;
  81.     for(i=n;i>=1;i--)
  82.     {
  83.         for(j=0;j<levels[i].size();j++)
  84.         {
  85.  
  86.              se.push_back((i-1)-(counts[levels[i][j]]-1));
  87.         }
  88.  
  89.     }
  90.    // cout<<se.size()<<endl;
  91.     sort(se.begin(),se.end());
  92.     l=0;
  93.     for(i=se.size()-1;i>=0;i--)
  94.     {
  95.           //cout<<se[i]<<" ";
  96.           if(l>=k)
  97.           break;
  98.           l++;
  99.           ans+=se[i];
  100.     }
  101.     cout<<ans<<endl;
  102.   }
  103.     return 0;
  104. }
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
11 7 
1 2 
2 3
2 4
3 5 
5 7 
5 8 
7 10 
7 11 
4 6 
6 9
stdout
copy 
22
https://ideone.com/8b7ZeU
language:
C++14 (gcc 8.3)
created:
4 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!