580. Cutting a Tree Into Even Pieces
Delete some edges of a tree, possibly none. Each remaining connected piece must contain an
EVEN number of nodes. Print the largest number of edges that can be deleted, or -1 when no
choice of deletions works.
4 nodes, edges 1-2 1-3 3-4 -> 1 cut 1-3, leaving {1,2} and {3,4}
5 nodes in a path -> -1 five is odd, so no split can work
## When it is impossible
The piece sizes add up to n, and a sum of even numbers is even. So if n is odd the answer is
-1, immediately and without looking at the tree at all.
If n is even, deleting nothing already works, so the answer is at least 0 and never -1.
## Which edges may be cut
Root at node 1. Every edge is a node u other than the root together with its parent, and
cutting it separates u's subtree from the rest.
Cut the edge above u exactly when size[u] is even.
That is the whole rule, and the answer is the count of non-root nodes with even subtree size.
## Why the rule is safe
The two claims that make this work are both short.
FIRST, each such cut is individually legal. If size[u] is even then the rest, n - size[u],
is even too, since n is even.
SECOND, cutting them ALL at once is still legal, and this is the part worth checking rather
than assuming. Consider any node u after every qualifying cut has been made. The piece
containing u is u's subtree minus the subtrees of every even-sized descendant that was cut
away, and each of those removed pieces is even. So the parity of u's piece equals the parity
of size[u]. When u was itself cut, size[u] is even and the piece is even. When u is the
root, size[u] = n is even. No piece is ever odd.
So the cuts never interfere, and no ordering or backtracking is needed.
## Why this is in a dynamic programming topic
Because the obvious approach is a table. You could carry, for each node, the best result with its piece currently even and with it currently odd, and that DP is correct.
Finding that the table is not needed is the lesson. The subtree sizes already contain the answer, and a single condition on each of them replaces the whole recurrence. Reaching for a table is a habit worth interrupting once per topic.
## Boundaries
A single node is odd, so the answer is -1.
Two nodes joined by an edge answer 0: the edge cannot be cut, since that would leave two pieces of size 1.
A star with an even number of nodes also answers 0, because every subtree below the centre has size 1.
## Cost
Time O(n). Space O(n).
Constraints - `1 ≤ n ≤ 100000` - the input is always a tree
Input
The first line contains an integer n, the number of nodes.
Each of the next n - 1 lines contains two integers u and v, an edge of
the tree. Nodes are numbered 1 to n and the tree is rooted at node 1.
Output
Print one integer, the largest number of edges that can be deleted, or -1 if it is impossible.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.