Soldering

The cows are playing with wires! The soldering technique the cows have learned attaches the end of one wire to the middle of another wire. (Soldering two wires end to end is not allowed.) Several wires may be soldered onto the same point.

Using this technique, the cows want to build an impressive structure. The structure is a tree made of $N$ connected vertices ($1 \le N \le 50{,}000$) and $N-1$ unit-length edges. Each edge is given by two integers $A$ and $B$ ($1 \le A \le N$, $1 \le B \le N$, $A \ne B$), the numbers of the vertices at its two ends.

To build the structure the cows must buy wires. Longer wires are more expensive: a wire of length $L$ costs $L \times L$. Wires may not be cut, nor spliced together into longer wires.

Given the blueprint of the structure, compute the minimum cost to build it by soldering wires.

Note: for 50% of the test data, $N < 2{,}000$.

• The first line contains the integer $N$.
• Each of the next $N-1$ lines contains two integers $A$ and $B$ describing an edge.

Print, on a single line, the minimum cost to build the structure. The answer may exceed the range of a 32-bit integer.

Consider a star in which every vertex is connected directly to vertex 1: you can join two edges into a single wire of length 2 and use a length-1 wire for each remaining edge. With 6 vertices the cost is $2^2 + 1^2 \times 3 = 7$.