fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.     ios::sync_with_stdio(false);
  6.     cin.tie(nullptr);
  7.     int n;
  8.     if (!(cin >> n)) return 0;
  9.     vector<int> col(n+1); // true = black, false = pink
  10.     for (int i = 1; i <= n; ++i) {
  11.         int x; cin >> x;
  12.         col[i] = (x == 1);
  13.     }
  14.     vector<vector<int>> g(n+1);
  15.     for (int i = 0; i < n-1; ++i) {
  16.         int a,b; cin >> a >> b;
  17.         g[a].push_back(b);
  18.         g[b].push_back(a);
  19.     }
  20.  
  21.     vector<int> parent(n+1, 0);
  22.     vector<int> ans;
  23.     ans.reserve(3*n);
  24.  
  25.     // iterative DFS using stack of (node, next_child_index)
  26.     vector<pair<int,int>> st;
  27.     st.emplace_back(1, 0);
  28.     ans.push_back(1);
  29.     col[1] = !col[1]; // visited node 1 at start -> flip
  30.  
  31.     while (!st.empty()) {
  32.         int v = st.back().first;
  33.         int &idx = st.back().second;
  34.  
  35.         if (idx < (int)g[v].size()) {
  36.             int u = g[v][idx++];
  37.             if (u == parent[v]) continue;
  38.             parent[u] = v;
  39.             // go to child u
  40.             ans.push_back(u);
  41.             col[u] = !col[u];
  42.             st.emplace_back(u, 0);
  43.         } else {
  44.             // finished all children of v, go back to parent (if any)
  45.             st.pop_back();
  46.             if (parent[v] != 0) {
  47.                 int p = parent[v];
  48.                 ans.push_back(p);            // move to parent
  49.                 col[p] = !col[p];
  50.                 // if child v is still pink, we need to revisit it and return again
  51.                 if (!col[v]) {
  52.                     ans.push_back(v);        // go to child again
  53.                     col[v] = !col[v];
  54.                     ans.push_back(p);        // return to parent
  55.                     col[p] = !col[p];
  56.                 }
  57.             }
  58.         }
  59.     }
  60.  
  61.     // special fix if root ended pink -> use any child of root
  62.     if (!col[1]) {
  63.         if (!g[1].empty()) {
  64.             int c = g[1][0];
  65.             ans.push_back(c); col[c] = !col[c];
  66.             ans.push_back(1); col[1] = !col[1];
  67.             ans.push_back(c); col[c] = !col[c];
  68.         }
  69.         // if root has no child (n==1), but it's pink -> impossible by problem statement constraints (solution guaranteed)
  70.     }
  71.  
  72.     // output sequence
  73.     for (size_t i = 0; i < ans.size(); ++i) {
  74.         if (i) cout << ' ';
  75.         cout << ans[i];
  76.     }
  77.     cout << '\n';
  78.     return 0;
  79. }
  80.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
5
1
1
-1
1
-1
2 5
4 3
2 4
4 1
stdout
copy 
1 4 3 4 2 5 2 4 1 4 1 4 1 4
https://ideone.com/kbv099
language:
C++14 (gcc 8.3)
created:
18 days 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!