fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define mod 1000000007//aacoder
  4. // aacoder codes 
  5. #define pb push_back //aacoder
  6.  
  7. using namespace std;
  8. vector<ll> aacoder[200008],value,childs,ans; //aacoder
  9.  
  10. void dfs(ll now, ll last){ //aacoder
  11.  
  12. for(ll i=0; i<aacoder[now].size(); i++){ //aacoder
  13.     // aacoder
  14.         ll child= aacoder[now][i]; //aacoder
  15.         if(child!=last) //aacoder
  16.         dfs(child,now); //aacoder
  17.     }
  18.     childs.clear();
  19.  
  20.     for(ll i=0; i<aacoder[now].size(); i++){  //aacoder
  21.         // aacoder
  22.         ll child= aacoder[now][i];  //aacoder
  23.         if(child!=last)
  24.         childs.push_back(value[child]); //aacoder
  25.     }
  26.     if(childs.size()>0){
  27.         sort(childs.begin(),childs.end()); //aacoder
  28.  
  29.         ll x=childs[0];  //aacoderhhuhik
  30.         // aacoderjnkj
  31.         ll checker=0; //aacoder
  32.         // aacoder
  33.         for(ll i=0; i<childs.size(); i++){  //aacoder
  34.             // aacoder  //aacoder pooji aacoderpokfjdfdfdfv
  35.             if(childs[i]!= x) checker++;  //aacoder
  36.             // aacoder
  37.         }
  38.         if(checker==0) value[now]+= x+1; //aacoder
  39.         // aacoder
  40.         if(checker!=0) value[now]+= x +2;      //aacoder
  41.     }
  42.     else
  43.     value[now]=0; //aacoder
  44. }
  45.  
  46.  
  47. void dfs1(ll node, ll par, ll minh){
  48.  
  49.     for(ll i=0; i<aacoder[node].size(); i++){  //aacoder
  50.         // aacoder
  51.         ll child= aacoder[node][i];
  52.         // snekar
  53.         minh = min(minh,value[node]);
  54.         if(child!=par){
  55.             if(value[child]>=minh-1){
  56.             dfs1(child,node,minh);
  57.             }
  58.         }
  59.     }
  60.     if(value[node]==0){
  61.     ans.push_back(node);
  62.     }
  63. }    
  64.  
  65. /* 
  66. code chef thanks  aacoder for the nice questions
  67. i think i did well in this aacoderpokfjdfdfdfv
  68. printf
  69. scanf 
  70. cin ,cout are same 
  71. */
  72.  
  73.  
  74.  
  75.  
  76. int main(){
  77. ios_base::sync_with_stdio(0);
  78.       cin.tie(0);
  79.  
  80. ll t = 1; cin >> t;
  81.     while(t--) {
  82.         ll N; cin >> N;
  83.  
  84. value.assign(N+1,0);
  85.  
  86.         for(ll i=0;i<N-1; i++)
  87.         {
  88.             int l, r;
  89.             cin >> l >> r;
  90.             aacoder[l].pb(r), aacoder[r].pb(l);
  91.         }
  92.  
  93.         dfs(1,0);
  94.  
  95.  
  96.  int minx = INT_MAX;
  97.  
  98.         for(ll i = 0; i<aacoder[1].size(); i++){
  99.             ll child = aacoder[1][i];
  100.             if(value[child]<minx){
  101.                 minx = value[child];
  102.             }
  103.         }
  104.  
  105.         for(ll i=0; i<aacoder[1].size(); i++){
  106.             // aacoder
  107.             ll child = aacoder[1][i];
  108.             if(value[child] == minx)
  109.             // aacoder
  110.             dfs1(child,1,minx);
  111.  
  112.         }
  113.  
  114.         sort(ans.begin(), ans.end());
  115.         // aacoder
  116.         cout<<ans.size()<<" "<<minx+1<<endl;//aacoder
  117.         // aacoder
  118.         for (ll i = 0; i <ans.size(); ++i) cout<<ans[i]<<" ";//aacoder
  119.         cout<<endl;
  120.  
  121.  
  122.         for (ll i = 1; i <=N; ++i) {aacoder[i].clear(); }
  123. // aacoder 
  124.        value.clear();
  125.        ans.clear();
  126.  
  127.  
  128.  
  129.  
  130.  
  131.     } 
  132.  
  133.     return 0;
  134.  
  135. }
Success #stdin #stdout 0.01s 8272KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
0 -2147483648
https://ideone.com/Zgec8l
language:
C++14 (gcc 8.3)
created:
3 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!