Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Only parity matters. Replace every by . A vertex is removable exactly when
Think of the removal order backwards. If is removed before , orient edge . Then the condition for depends only on its outgoing neighbors:
Since the graph is a tree, every orientation is automatically compatible with some removal order.
Root the tree. For an edge between a node and its parent, the only unresolved choice for the child is whether that edge points upward or downward. Once that one bit is fixed, the child can independently choose directions to its children, but only certain combinations satisfy its parity equation.
For a vertex , split its children by parity. Edges to even children contribute no matter their direction; edges to odd children contribute exactly when they point from to that child. So if there is at least one odd child whose edge direction is free, can flip the parity however it wants.
Use tree DP over edge directions. Let mean the subtree of can be oriented if the parent edge direction has when and when . Combine children greedily: choose any valid child state first, then if 's parity is wrong, flip one valid odd child that supports both states. If no flip exists, the state is impossible.
Only the parities of the values matter, so define
At some moment, vertex is removable iff
Now take the whole removal order and orient every edge from the earlier removed endpoint to the later removed endpoint. Then the remaining neighbors of at its deletion time are exactly the outgoing neighbors of . So we need an orientation of every edge such that
for every vertex .
And because the graph is a tree, this is not secretly hiding an ordering problem. Any orientation of a tree is acyclic, so we can topologically sort it and remove vertices in that order. That order satisfies exactly the same equations. Nice: the process becomes a static parity-orientation problem.
Root the tree at vertex . For a non-root vertex , the edge to its parent can be oriented in one of two ways:
Let mean: the whole subtree of can be oriented validly, assuming the parent edge has state from 's point of view. For the root, there is no parent edge, so we can treat its parent contribution as .
Suppose we are checking vertex under a fixed parent state . The parity currently required at is
That is the required parity of the sum of outgoing-neighbor labels.
The parent edge contributes if , otherwise . Each child edge contributes iff it is oriented . In the child's DP state, that means , because from the child's point of view the parent edge is .
For every child, we must pick a valid state:
If , the choice never changes 's parity. It only matters for feasibility inside the child's subtree.
If , choosing state toggles 's parity, while choosing state does not. So an odd child with both states valid is a parity switch. That's the whole trick. If your current choices make wrong, flip one such odd child. If no such child exists, this fixed parent state is impossible.
For each and parent state , we greedily choose one valid state for every child. Prefer state when possible, because it contributes to . If state is impossible, use state . Track the resulting parity. Also remember any odd child where both states are valid; that child can be flipped later. If the final parity is wrong, flip that child. If no flip exists, .
This greedy is enough because the only thing the parent cares about is one bit: the parity at . Child subtrees are independent once their parent-edge state is chosen. There is no weighted optimization, no lexicographic drama, no hidden flow problem. Just one damn bit.
After computing DP bottom-up, reconstruct one valid orientation top-down. The root has no parent contribution, so do the same child-choice procedure for it with initial parent contribution . If that succeeds, recurse into each child with the chosen state.
Finally, convert the orientation into a removal order. Since every edge is directed from earlier removed to later removed, any topological order of this directed tree works. We can compute indegrees and run a queue.
Edge cases:
Complexity is linear: each vertex and edge is processed a constant number of times.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<int> b(n + 1);
for (int i = 1; i <= n; i++) {
ll x;
cin >> x;
b[i] = x & 1;
}
vector<vector<int>> g(n + 1);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> parent(n + 1, 0), order;
order.reserve(n);
stack<int> st;
st.push(1);
parent[1] = -1;
while (!st.empty()) {
int v = st.top();
st.pop();
order.push_back(v);
for (int to : g[v]) {
if (to == parent[v]) continue;
parent[to] = v;
st.push(to);
}
}
vector<array<char, 2>> dp(n + 1);
auto build_choices = [&](int v, int parent_state,
vector<pair<int, int>> *chosen) -> bool {
int cur = 0;
if (parent_state == 1 && parent[v] != -1) cur ^= b[parent[v]];
int flip_child = -1;
if (chosen) chosen->clear();
for (int to : g[v]) {
if (to == parent[v]) continue;
int state = -1;
if (dp[to][1]) state = 1; // child -> v, contributes 0 to v
else if (dp[to][0]) state = 0; // v -> child
else return false;
if (state == 0) cur ^= b[to];
if (b[to] && dp[to][0] && dp[to][1]) flip_child = to;
if (chosen) chosen->push_back({to, state});
}
int need = 1 ^ b[v];
if (cur != need) {
if (flip_child == -1) return false;
for (auto &[to, state] : *chosen) {
if (to == flip_child) {
state ^= 1;
break;
}
}
}
return true;
};
for (int i = n - 1; i >= 0; i--) {
int v = order[i];
for (int s = 0; s < 2; s++) {
dp[v][s] = build_choices(v, s, nullptr);
}
}
vector<pair<int, int>> directed;
directed.reserve(n - 1);
vector<pair<int, int>> root_choices;
bool ok = build_choices(1, 0, &root_choices);
if (!ok) {
cout << "NO\n";
continue;
}
queue<pair<int, vector<pair<int, int>>>> q;
q.push({1, root_choices});
while (!q.empty()) {
int v = q.front().first;
auto choices = move(q.front().second);
q.pop();
for (auto [to, state] : choices) {
if (state == 0) directed.push_back({v, to});
else directed.push_back({to, v});
vector<pair<int, int>> nxt;
bool good = build_choices(to, state, &nxt);
if (!good) ok = false;
q.push({to, move(nxt)});
}
}
if (!ok) {
cout << "NO\n";
continue;
}
vector<vector<int>> dag(n + 1);
vector<int> indeg(n + 1, 0);
for (auto [u, v] : directed) {
dag[u].push_back(v);
indeg[v]++;
}
queue<int> topo;
for (int i = 1; i <= n; i++) {
if (indeg[i] == 0) topo.push(i);
}
vector<int> ans;
ans.reserve(n);
while (!topo.empty()) {
int v = topo.front();
topo.pop();
ans.push_back(v);
for (int to : dag[v]) {
if (--indeg[to] == 0) topo.push(to);
}
}
cout << "YES\n";
for (int v : ans) cout << v << ' ';
cout << '\n';
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<int> b(n + 1);
for (int i = 1; i <= n; i++) {
ll x;
cin >> x;
b[i] = x & 1;
}
vector<vector<int>> g(n + 1);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> parent(n + 1, 0), order;
order.reserve(n);
stack<int> st;
st.push(1);
parent[1] = -1;
while (!st.empty()) {
int v = st.top();
st.pop();
order.push_back(v);
for (int to : g[v]) {
if (to == parent[v]) continue;
parent[to] = v;
st.push(to);
}
}
vector<array<char, 2>> dp(n + 1);
auto build_choices = [&](int v, int parent_state,
vector<pair<int, int>> *chosen) -> bool {
int cur = 0;
if (parent_state == 1 && parent[v] != -1) cur ^= b[parent[v]];
int flip_child = -1;
if (chosen) chosen->clear();
for (int to : g[v]) {
if (to == parent[v]) continue;
int state = -1;
if (dp[to][1]) state = 1; // child -> v, contributes 0 to v
else if (dp[to][0]) state = 0; // v -> child
else return false;
if (state == 0) cur ^= b[to];
if (b[to] && dp[to][0] && dp[to][1]) flip_child = to;
if (chosen) chosen->push_back({to, state});
}
int need = 1 ^ b[v];
if (cur != need) {
if (flip_child == -1) return false;
for (auto &[to, state] : *chosen) {
if (to == flip_child) {
state ^= 1;
break;
}
}
}
return true;
};
for (int i = n - 1; i >= 0; i--) {
int v = order[i];
for (int s = 0; s < 2; s++) {
dp[v][s] = build_choices(v, s, nullptr);
}
}
vector<pair<int, int>> directed;
directed.reserve(n - 1);
vector<pair<int, int>> root_choices;
bool ok = build_choices(1, 0, &root_choices);
if (!ok) {
cout << "NO\n";
continue;
}
queue<pair<int, vector<pair<int, int>>>> q;
q.push({1, root_choices});
while (!q.empty()) {
int v = q.front().first;
auto choices = move(q.front().second);
q.pop();
for (auto [to, state] : choices) {
if (state == 0) directed.push_back({v, to});
else directed.push_back({to, v});
vector<pair<int, int>> nxt;
bool good = build_choices(to, state, &nxt);
if (!good) ok = false;
q.push({to, move(nxt)});
}
}
if (!ok) {
cout << "NO\n";
continue;
}
vector<vector<int>> dag(n + 1);
vector<int> indeg(n + 1, 0);
for (auto [u, v] : directed) {
dag[u].push_back(v);
indeg[v]++;
}
queue<int> topo;
for (int i = 1; i <= n; i++) {
if (indeg[i] == 0) topo.push(i);
}
vector<int> ans;
ans.reserve(n);
while (!topo.empty()) {
int v = topo.front();
topo.pop();
ans.push_back(v);
for (int to : dag[v]) {
if (--indeg[to] == 0) topo.push(to);
}
}
cout << "YES\n";
for (int v : ans) cout << v << ' ';
cout << '\n';
}
return 0;
}