Submission #38985570

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

struct Node {
int n;
bool b{};
vector<Node *> edge;
void shuffle(deque<int> &q) {
  b = true;
  bool first = true;
  for (auto e : edge) {
    if (e->b) continue;
    if (first) {
      first = false;
      q.push_back(n);
      e->shuffle(q);
      n = q.front();
      q.pop_front();
    } else {
      deque<int> p;
      p.push_back(n);
      e->shuffle(p);
      n = p.front();
      p.pop_front();
    }
  }
  if (first) {
    q.push_back(n);
    n = q.front();
    q.pop_front();
  }
}
};

int main() {
  int N;
  cin >> N;
  vector<Node> node(N);
  for (int n = 0; n < N; ++n) {
    node[n].n = n+1;
  }
  for (int n = 0; n < N - 1; ++n) {
    int u, v;
    cin >> u >> v;
    --u; --v;
    node[u].edge.push_back(&node[v]);
    node[v].edge.push_back(&node[u]);
  }
  Node *start = &node[0];
  int prev = -1;
  while (start->edge.size() != 1) {
    for (auto n : start->edge) {
      if (n->n != prev) {
        start = n;
        prev = start->n;
        break;
      }
    }
  }
  deque<int> q;
  start->shuffle(q);
  for (int n = 0; n < N; ++n) {
    cout << node[n].n << " ";
  }
  cout << endl;
}

Submission Info

Judge Result