570. Adding Up Every Pair Distance
Print the total, over every UNORDERED pair of distinct nodes, of the number of edges on the shortest path between them.
4 nodes, edges 1-2 1-3 3-4 -> 10
5 nodes in a star -> 16
## Do not compute distances at all
The direct reading is a table of n^2 distances. At n = 100000 that table does not fit in
memory, let alone finish, so the table is the wrong object.
Turn the sum inside out. Instead of asking "how far apart is each pair", ask of each EDGE: how many pairs use it?
Every pair's path is a set of edges, so summing over pairs the number of edges used is the same as summing over edges the number of pairs using them. Both count the same (pair, edge) incidences, just grouped differently.
## What one edge is worth
Removing a single edge splits a tree into exactly two pieces. A pair uses that edge precisely when its two nodes are in different pieces, so the count for that edge is
(size of one piece) * (size of the other)
Root at node 1. Every edge joins some node u other than the root to its parent, and the two
pieces are u's subtree and everything else:
answer = sum over u != root of size[u] * (n - size[u])
size[u] comes from one children-first sweep. That is the entire solution: one pass, no
distance is ever computed, and nothing quadratic is ever built.
## Why this is the lesson
Most of dynamic programming is about filling a table efficiently. This problem is about noticing that the table asked for is not the table needed.
Regrouping a double sum by the inner object, rather than the outer one, is a standard move, and on trees the inner object is almost always an edge.
## Boundaries
One node has no pairs, so the answer is 0. Two nodes have one pair at distance 1.
A star of n nodes answers (n-1) + 2 * C(n-1, 2): each leaf is 1 from the centre and 2 from
every other leaf. For n = 5 that is 4 + 2 * 6 = 16, which is the sample.
## Cost
Time O(n). Space O(n).
The total can be about 100000^3 / 4, so accumulate in 64 bits. A 32 bit accumulator
silently wraps on the larger tests.
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 sum of the distances over all unordered pairs of distinct nodes.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.