fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 2e5 + 5;
  6. set<int> g[N];
  7. int h[N], parent[N];
  8.  
  9.  
  10. struct triple {
  11.     int a, b, c, d;
  12. };
  13.  
  14.  
  15. void dfs(int v, int curh) {
  16.     h[v] = curh;
  17.     for (auto u: g[v]) {
  18.         if (u != parent[v]) {
  19.             parent[u] = v;
  20.             dfs(u, curh + 1);
  21.         }
  22.     }
  23. }
  24.  
  25. void get(int idx, int& b, int& c, int& d) {
  26.     b = *g[idx].begin();
  27.     g[idx].erase(b);
  28.     c = *g[idx].begin();
  29.     g[idx].erase(c);
  30.     d = *g[idx].begin();
  31.     g[idx].erase(d);
  32. }
  33.  
  34. int main() {
  35.     //freopen("input.txt", "r", stdin);
  36.     ios_base::sync_with_stdio(false);
  37.     int cases;
  38.     cin >> cases;
  39.     while (cases--) {
  40.         int n;
  41.         cin >> n;
  42.         vector<triple> ans;
  43.         set<pair<int, int>> s;
  44.         for (int i = 1; i <= n; ++i) {
  45.             g[i].clear();
  46.             parent[i] = 0;
  47.         }
  48.         for (int i = 1; i <= n - 1; ++i) {
  49.             int v, u;
  50.             cin >> v >> u;
  51.             g[v].insert(u);
  52.             g[u].insert(v);
  53.         }
  54.         dfs(1, 0);
  55.         for (int i = 1; i <= n; ++i) {
  56.             if (i != 1) {
  57.                 g[i].erase(parent[i]);
  58.             }
  59.         }
  60.  
  61.  
  62.         for (int i = 2; i <= n; ++i) {
  63.             s.insert(make_pair(h[i], i));
  64.         }
  65.         string res = "YES";
  66.         while (!s.empty()) {
  67.             auto it = s.rbegin();
  68.             int v = it->second;
  69.             int p = parent[v];
  70.             if (p == 1) {
  71.                 if (g[p].size() % 3 != 0) {
  72.                     res = "NO";
  73.                     break;
  74.                 }
  75.                 int sz = int(g[1].size());
  76.                 for (int i = 1; i <= sz / 3; ++i) {
  77.                     int b, c, d;
  78.                     get(1, b, c, d);
  79.                     ans.emplace_back(triple{1, b, c, d});
  80.                 }
  81.                 break;
  82.             } else {
  83.                 if (g[p].size() % 3 == 1) {
  84.                     res = "NO";
  85.                     break;
  86.                 }
  87.                 while (g[p].size() >= 3) {
  88.                     int b, c, d;
  89.                     get(p, b, c, d);
  90.                     g[b].erase(p);
  91.                     g[c].erase(p);
  92.                     g[d].erase(p);
  93.                     ans.emplace_back(triple{p, b, c, d});
  94.                     s.erase(make_pair(h[b], b));
  95.                     s.erase(make_pair(h[c], c));
  96.                     s.erase(make_pair(h[d], d));
  97.                 }
  98.                 if (g[p].size() == 2) {
  99.                     int d = parent[p];
  100.                     auto it = g[p].begin();
  101.                     int b = *it;
  102.                     ++it;
  103.                     int c = *it;
  104.                     g[p].clear();
  105.                     g[b].erase(p);
  106.                     g[c].erase(p);
  107.                     g[d].erase(p);
  108.                     ans.emplace_back(triple{p, b, c, d});
  109.                     s.erase(make_pair(h[p], p));
  110.                     s.erase(make_pair(h[b], b));
  111.                     s.erase(make_pair(h[c], c));
  112.                     g[p].clear();
  113.                 }
  114.             }
  115.         }
  116.         cout << res << "\n";
  117.         if (res == "YES") {
  118.             for (size_t j = 0; j < ans.size(); ++j) {
  119.                 cout << ans[j].a << " " << ans[j].b << " " << ans[j].c << " " << ans[j].d << "\n";
  120.             }
  121.         }
  122.     }
  123. }
  124.  
Runtime error #stdin #stdout 0s 12324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rZnxYK
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!