The Best Place to Stand
For a node v, its REACH is the total number of edges on the shortest paths from v to
every node of the tree, itself included. Print the smallest reach any node has.
4 nodes, edges 1-2 1-3 3-4 -> 4 standing at node 1 costs 0 + 1 + 1 + 2
5 nodes in a star -> 4 the centre reaches four leaves at distance 1
## The obvious method is too slow
A breadth first search from a node gives its reach in O(n). Doing that from all n nodes is
O(n^2), which at n = 100000 is ten billion steps.
The whole point of this problem is the technique that turns those n searches into two passes.
## Pass one: reach within the subtree
Root the tree at node 1 and compute, for every node, two numbers by the usual children-first sweep:
size[u] = the number of nodes in u's subtree
down[u] = total distance from u to every node in its own subtree
size[u] = 1 + sum over children c of size[c]
down[u] = sum over children c of (down[c] + size[c])
The + size[c] is the part worth pausing on. Every node in c's subtree is one edge further
from u than it is from c, and there are size[c] of them, so the whole subtree's contribution
grows by exactly size[c].
down[1] is already the reach of the root, because the root's subtree is everything.
## Pass two: carry the answer downwards
Now go the OTHER way, parents before children, and convert a parent's full answer into its
child's. Moving the standing point from u to a child c:
· the size[c] nodes inside c's subtree each get one edge CLOSER
· the other n - size[c] nodes each get one edge FURTHER
ans[1] = down[1]
ans[c] = ans[u] - size[c] + (n - size[c])
That is the whole of rerooting: one sweep upwards to collect subtree facts, one sweep
downwards to turn the root's answer into everybody's. It is the tree analogue of a prefix and
a suffix pass over an array, and it is what makes an O(n^2) family of questions O(n).
The answer is the smallest entry of ans.
## The fill order, twice
The first pass needs children before parents, so walk the traversal order backwards. The second needs parents before children, so walk the SAME order forwards. Getting one of them the wrong way round reads entries that have not been written, exactly as a mis-ordered interval table does.
## Boundaries
One node has reach 0: it reaches only itself, at distance 0.
On a path of eight nodes the answer is 16, at either of the two middle nodes, and the two of them tie. The problem asks only for the value, so the tie needs no rule.
## Cost
Time O(n). Space O(n).
A reach can be about 100000 times 100000, so accumulate in 64 bits.