Hints: The 67th Tree Problem

Let $n = x + y$. Root the tree at node $1$ and recall “subtree size of $u$” means $|T_u|$.

What is the subtree size of a leaf $u \neq 1$? What parity does that force?

Answer to Hint 1: A leaf $u \neq 1$ has $|T_u| = 1$, which is odd. So every non-root leaf is a vertex whose subtree size is odd.

What inequality must hold between $x$ and $y$, comparing “how many even-subtree nodes you want” to “how many odd-subtree nodes you need at minimum”?

Any tree with $n \ge 2$ has at least two leaves, and (except for the root) those leaves have odd subtree size. Use that to compare $x$ and $y$.

When should you output NO immediately from this kind of counting?

Answer to Hint 2: You must have $x \le y$: there cannot be more even-subtree vertices than odd-subtree vertices in this sense. Concretely, if $x > y$, output NO.

Next, look at the root: $|T_1| = n$. Does the root’s parity depend on anything besides $n$?

If $n$ is even, then $|T_1|$ is even, so vertex $1$ always counts toward $x$.

Can you have no even-subtree vertex at all in that situation?

Answer to Hint 3: No. If $n$ is even, the root itself is an even-subtree vertex, so $x = 0$ is impossible. Thus if $n$ is even and $x = 0$, output NO.

Together with $x \le y$, these are the standard quick impossibility checks; otherwise, try to construct.

Think about building a path (a chain) from the root: if you only extend the tree at the current deepest vertex, subtree sizes along the path are easy to reason about.

What happens to the parities of $|T_u|$ on the path when you attach one new leaf to the deepest vertex?

Answer to Hint 4: Adding a leaf under a vertex increases its subtree size by $1$, flipping its parity—and the same flip propagates to every ancestor, including the root.

So you can first grow a path to “spend” the even-subtree budget in a controlled way, then attach the remaining vertices as further leaves from the tail to finish the odd-subtree budget.

Try: extend a path $1\text{--}2\text{--}\cdots$ while updating how many even- and odd-subtree vertices you still need, using the parity of the next vertex’s subtree size and the parity of the current total size.

When the even budget hits zero, attach each remaining new vertex as a leaf to the current endpoint until all requirements are met.

How do you bookkeep $(x, y)$ and $n$ after fixing the root’s contribution?

Answer to Hint 5: Let $n = x + y$. First account for vertex $1$: if $n$ is even, decrement $x$; if $n$ is odd, decrement $y$. Then set $n \leftarrow n - 1$ (one vertex is already placed).

While you still need even-subtree vertices along the growing path, add an edge to a new vertex, update $n$, and decrement $x$ or $y$ according to whether the new vertex’s subtree size is even or odd under your attachment rule.

When $x = 0$, only add leaves hanging from the current tail: each new leaf is odd-subtree, and the tail’s subtree parity updates predictably as leaves are appended one by one until $y$ is exhausted.