fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int MAXN=3e6+5;
  5. vector<int>G[MAXN];
  6. vector<int>ans[MAXN];
  7. int kept[MAXN];
  8. int n,k;
  9. int main()
  10. {
  11.     cin>>n>>k;
  12.     for(int i=0; i<n-1; i++)
  13.     {
  14.         int u,v;
  15.         cin>>u>>v;
  16.         G[u].push_back(v);
  17.         G[v].push_back(u);
  18.     }
  19.     queue<pair<int,int>>q;
  20.     for(int i=1; i<=n; i++)
  21.     {
  22.         kept[i]=G[i].size();
  23.         if(G[i].size()==1)
  24.         {
  25.             q.push({i, 0});
  26.         }
  27.     }
  28.     while(!q.empty())
  29.     {
  30.         pair<int,int>p=q.front();
  31.         int level=p.second;
  32.         int v=p.first;
  33.         q.pop();
  34.         ans[level].push_back(v);
  35.         for(int i : G[v])
  36.         {
  37.             kept[i]--;
  38.             if(kept[i]==1)
  39.             {
  40.                 q.push({i, level+1});
  41.                 kept[v]--;
  42.             }
  43.         }
  44.  
  45.     }
  46.     /*for(int i=0; i<n; i++)
  47.     {
  48.         for(int j : ans[i])
  49.         {
  50.             cout<<j<<" ";
  51.         }
  52.         cout<<"\n";
  53.     }*/
  54.     for(int i=0; i<n; i++)
  55.     {
  56.         if(ans[i].size()<=k)
  57.         {
  58.             if (ans[i].size() == 1) {
  59.                 int v = ans[i][0];
  60.                 ans[i].push_back(G[v][0]);
  61.             }
  62.  
  63.             cout<<i<<" "<<ans[i].size()<<"\n";
  64.             for(int j=0; j<ans[i].size(); j++)
  65.             {
  66.                 cout<<ans[i][j]<<" ";
  67.             }
  68.             break;
  69.         }
  70.     }
  71.     return 0;
  72. }
  73.  
Success #stdin #stdout 0.04s 144660KB
comments (?)
stdin
copy 
8 3
1 5
2 5
2 7
3 7
4 5
5 6
7 8
stdout
copy 
1 2
5 7
https://ideone.com/RYk8m6
language:
C++14 (gcc 8.3)
created:
237 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!