fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define f first
  4. #define s second
  5. #define pb push_back
  6. #define pob pop_back
  7. #define b back
  8. #define cout(x) cout << x << endl
  9. #define lb long double
  10. #define soa(arr, n) sort(arr,arr+n)
  11. #define inputVector(v, n) for(int i = 0; i < n; i++) cin >> v[i]
  12. #define sov(v) sort(v.begin(), v.end())
  13. #define rev(v) reverse(v.begin(), v.end())
  14. #define pl pair<ll, ll>
  15. #define all(a)    a.begin(), a.end()
  16. #define vpp vector<pair<ll, ll>>
  17. #define fastIo ios_base::sync_with_stdio(false), cin.tie(0)
  18. #define endl '\n'
  19. #include <ext/pb_ds/assoc_container.hpp>
  20. #include <ext/pb_ds/tree_policy.hpp>
  21. using namespace __gnu_pbds;
  22.  
  23. #define ordered_set tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update>
  24. typedef long long int  ll;
  25. ll P = 1e9 + 7;
  26. vector<ll> adj[300001];
  27. priority_queue<ll,  vector<ll>, greater<ll>> pq;
  28. ll isLeaf(vector<ll> & vis, ll u) {
  29.     vis[u] = 1;
  30.     ll ans = 1;
  31.     ll leaf = 0;
  32.     ll vv = 0;
  33.     for(auto v: adj[u]) {
  34.         if(!vis[v]) {
  35.             leaf = 1;
  36.             ans &= isLeaf(vis, v);
  37.             vv += 1;
  38.         }
  39.     }
  40.     if(ans && vv) {
  41.         pq.push(vv);
  42.     }
  43.     return !leaf;
  44. }
  45.  
  46. void solve() {
  47.     ll  n, q, k, l, x, y, m;
  48.     cin >> n;
  49.     for(ll i = 1; i <= n; i ++) {
  50.         adj[i].clear();
  51.     }
  52.  
  53.     for(ll i = 1; i < n; i ++) {
  54.         cin >> x >> y;
  55.         adj[x].pb(y);
  56.     }
  57.     vector<ll> vis(n + 1);
  58.     isLeaf(vis, 1);
  59.     while(pq.size() > 1) {
  60.         auto u = pq.top();
  61.         pq.pop();
  62.         auto v = pq.top();
  63.         pq.pop();
  64.         pq.push(u + v -1);
  65.     }
  66.     if(pq.size() > 0) {
  67.     cout << pq.top() << endl;
  68.     pq.pop();
  69.     }
  70.     else {
  71.         cout << 1 << endl;
  72.     }
  73.  
  74. }
  75.  
  76.  
  77. int main() {
  78.     ll t=1,i=1;
  79.     fastIo;
  80.     cin >> t;
  81.     while(t--) {
  82.         // cout << "Case #" << i << ": ";
  83.         solve();
  84.         i++;
  85.     }
  86.     return 0;
  87. }
  88. // 2 3 5 6 7 10 11 13 15 17 19 21 22 23 25 26 29 30
  89.  
Success #stdin #stdout 0.01s 10624KB
comments (?)
stdin
copy 
5
7
1 2
1 3
1 4
2 5
2 6
4 7
6
1 2
1 3
2 4
2 5
3 6
2
1 2
7
7 3
1 5
1 3
4 6
4 7
2 1
6
2 1
2 3
4 5
3 4
3 6
stdout
copy 
2
2
1
2
1
https://ideone.com/ngaPsL
language:
C++14 (gcc 8.3)
created:
2 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!