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 subtree-size parity matters. For a node ,
So is even exactly when it has an odd number of odd-subtree children.
Every even node needs at least one odd child. Those odd children are all distinct and non-root, so if the root is odd, you cannot use it for this job. That gives a nasty-looking but simple bound.
Let and . The root is odd iff . Since every even node needs a distinct non-root odd child,
Also, if is even, the root itself is even, so .
The construction can use only two kinds of edges: make all even nodes into one chain, and attach odd leaves. Even-child subtrees do not affect parity, while each odd leaf toggles the parent’s odd-child count.
Final recipe:
The leftover count is always even, which is the whole damn trick.
Let be the size of the subtree of node . Then
Modulo ,
Therefore:
So every even node must have at least one odd child. No exceptions. Leaves are odd, as usual.
Let
and let
The root has subtree size , so the root is odd iff .
Every even node needs at least one odd child. These chosen odd children are distinct, because every non-root node has exactly one parent. Also, the root cannot be anyone's child, so only non-root odd nodes are available.
The number of non-root odd nodes is
Hence we must have
Also, when is even, the root itself is even, so we need
Thus the full condition is:
Now we prove those conditions are sufficient.
The root must be even. Since the condition gives , make a chain of even nodes starting from node :
Attach one odd leaf to every . Now every even node has exactly one odd child, so each is even. The even child below it does not affect parity.
This uses odd leaves. We still need
more odd nodes. Since is even, and have the same parity, so is even. Attach all these remaining nodes as leaves to the root. The root already had one odd leaf; adding an even number of odd leaves keeps its number of odd children odd, so it stays even.
Counts are exactly:
The root must be odd. Make a chain of even nodes below the root:
Attach one odd leaf to every . Again, all are even.
We have used odd root plus odd leaves, so the remaining odd leaves needed are
The condition makes this nonnegative, and since is odd, is even. Attach all remaining odd leaves to the root. The root has an even number of odd children, so it stays odd. Nice and clean.
For each test case we output exactly edges and do work:
per test case, and over all tests:
Memory usage is also linear in the number of edges for the current test case, though you could stream the edges directly if you really wanted to min-max the boring stuff.
#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 x, y;
cin >> x >> y;
int n = x + y;
bool ok;
if (n % 2 == 0) {
ok = (x >= 1 && x <= y);
} else {
ok = (x < y);
}
if (!ok) {
cout << "NO\n";
continue;
}
cout << "YES\n";
vector<pair<int, int>> edges;
vector<int> even_nodes;
int nxt = 2;
if (n % 2 == 0) {
// Root is even. Build a chain of x even nodes starting at 1.
even_nodes.push_back(1);
for (int i = 1; i < x; i++) {
int v = nxt++;
edges.push_back({even_nodes.back(), v});
even_nodes.push_back(v);
}
// One odd leaf for every even node.
for (int v : even_nodes) {
edges.push_back({v, nxt++});
}
// y - x is even, so attaching these to root preserves root parity.
for (int i = 0; i < y - x; i++) {
edges.push_back({1, nxt++});
}
} else {
// Root is odd. Build x even nodes below it.
int prev = 1;
for (int i = 0; i < x; i++) {
int v = nxt++;
edges.push_back({prev, v});
even_nodes.push_back(v);
prev = v;
}
// One odd leaf for every even node.
for (int v : even_nodes) {
edges.push_back({v, nxt++});
}
// y - 1 - x is even, so root remains odd.
for (int i = 0; i < y - 1 - x; i++) {
edges.push_back({1, nxt++});
}
}
for (auto [u, v] : edges) {
cout << u << ' ' << v << '\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 x, y;
cin >> x >> y;
int n = x + y;
bool ok;
if (n % 2 == 0) {
ok = (x >= 1 && x <= y);
} else {
ok = (x < y);
}
if (!ok) {
cout << "NO\n";
continue;
}
cout << "YES\n";
vector<pair<int, int>> edges;
vector<int> even_nodes;
int nxt = 2;
if (n % 2 == 0) {
// Root is even. Build a chain of x even nodes starting at 1.
even_nodes.push_back(1);
for (int i = 1; i < x; i++) {
int v = nxt++;
edges.push_back({even_nodes.back(), v});
even_nodes.push_back(v);
}
// One odd leaf for every even node.
for (int v : even_nodes) {
edges.push_back({v, nxt++});
}
// y - x is even, so attaching these to root preserves root parity.
for (int i = 0; i < y - x; i++) {
edges.push_back({1, nxt++});
}
} else {
// Root is odd. Build x even nodes below it.
int prev = 1;
for (int i = 0; i < x; i++) {
int v = nxt++;
edges.push_back({prev, v});
even_nodes.push_back(v);
prev = v;
}
// One odd leaf for every even node.
for (int v : even_nodes) {
edges.push_back({v, nxt++});
}
// y - 1 - x is even, so root remains odd.
for (int i = 0; i < y - 1 - x; i++) {
edges.push_back({1, nxt++});
}
}
for (auto [u, v] : edges) {
cout << u << ' ' << v << '\n';
}
}
return 0;
}