Ankit_132

E

May 27th, 2023 (edited)
191
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.37 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll     long long
  6. #define ff     first
  7. #define ss     second
  8. #define pb     push_back
  9.  
  10. int main()
  11. {
  12.  
  13.     int n;
  14.     cin>>n;
  15.  
  16.     vector<set<int>> tree(n);
  17.     vector<int> connected(n);
  18.  
  19.     for(int i=0; i<n-1; i++)
  20.     {
  21.         int u, v;
  22.         cin>>u>>v;
  23.  
  24.         u--, v--;
  25.  
  26.         tree[u].insert(v);
  27.         tree[v].insert(u);
  28.  
  29.         connected[u]++;
  30.         connected[v]++;
  31.     }
  32.  
  33.     set<pair<int, int>> sp;
  34.  
  35.     for(int i=0; i<n; i++)
  36.         sp.insert({connected[i], i});
  37.  
  38.     vector<int> x;
  39.     vector<int> done(n);
  40.  
  41.     while(sp.size() && (*sp.begin()).ff == 1)
  42.     {
  43.         auto e = *sp.begin();
  44.         sp.erase(sp.begin());
  45.         if(done[e.ss])      continue;
  46.  
  47.         done[e.ss] = 1;
  48.         int u = *tree[e.ss].begin();
  49.  
  50.         x.pb(u);
  51.  
  52.         for(auto v: tree[u])
  53.         {
  54.             done[v] = 1;
  55.  
  56.             for(auto c: tree[v])
  57.             {
  58.                 if(c == u)      continue;
  59.  
  60.                 sp.erase({connected[c], c});
  61.                 connected[c]--;
  62.                 sp.insert({connected[c], c});
  63.  
  64.                 tree[c].erase(v);
  65.             }
  66.         }
  67.     }
  68.  
  69.     vector<int> ans;
  70.     for(auto e: x)
  71.         ans.pb(tree[e].size());
  72.  
  73.     sort(ans.begin(), ans.end());
  74.  
  75.     for(auto e: ans)
  76.       cout<<e<<" ";
  77.   cout<<"\n";
  78. }
  79.  
Advertisement
Add Comment
Please, Sign In to add comment