569. 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.

Constraints - `1 ≤ n ≤ 100000` - the input is always a tree