572. Removing the Node That Splits It Best
Remove exactly ONE node from a tree, along with every edge touching it. What remains is a collection of pieces. Print the smallest possible size of the LARGEST piece, over all choices of node.
4 nodes, edges 1-2 1-3 3-4 -> 2 removing node 1 leaves {2} and {3,4}
5 nodes in a star -> 1 removing the centre leaves four single nodes
## What the pieces are
Root at node 1. Removing node u leaves one piece for each child of u, namely that child's
subtree, and, when u is not the root, ONE more piece: everything that was above u.
That last piece is the part people forget, and it has a short formula:
size of the piece above u = n - size[u]
because the tree has n nodes, size[u] of them are in u's subtree, and removing u leaves
the rest connected through the parent.
## The scan
One children-first sweep gives every size[u]. Then, for each u:
largest(u) = max( n - size[u], max over children c of size[c] )
and the answer is the smallest largest(u).
For the root, n - size[1] is 0, which is harmless inside a maximum, so the formula needs no
special case.
## What this node is
The node achieving the minimum is called a CENTROID, and it always satisfies
largest <= n / 2. That bound is worth knowing but it is not needed here: the scan finds the
minimum directly, whatever it turns out to be.
A tree can have two centroids, on a path of an even number of nodes for instance. The problem asks for the SIZE, not the node, so the tie needs no rule.
## Boundaries
A single node removed leaves nothing at all, so the answer is 0. A solution that takes a maximum over an empty list must start that maximum at 0 rather than at a large sentinel.
On a path of eight the answer is 4: removing either middle node leaves pieces of 3 and 4.
## 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 smallest possible size of the largest remaining piece.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.