题目描述

The cows are playing with wires! They have learned a technique called soldering, in which they connect two pieces of wire together by attaching the endpoint of one wire to a location along the length of the other. (Soldering endpoint to endpoint is not allowed.) There can be multiple solder junctions at the same point.

The cows have a plan for an Amazing Structure they would like to build. It is in the form of a graph with $N$($1 \leq N \leq 50,000$) nodes and $N - 1$ edges of unit length so that each pair of nodes is connected. Each edge is described by a pair of integers, $A$ and $B$($1 \leq A \leq N; 1 \leq B \leq N; A \neq B$).

The cows are able to buy wire from a local store; however longer wire is more expensive. In particular the cows can buy a wire of length L with cost $L * L$, but they cannot cut wires or join wires together.

Given the plan, the cows would like solder wires together to build their Amazing Structure. Please help them find the minimum possible cost!

输入格式

Line $1$: A single integer: $N$

Lines $2 \sim N$: Two space-separated integers describing an edge: $A$ and $B$

输出格式

Line $1$: A single integer, the cost of soldering the tree together.

Note that this number may not always fit in a 32-bit integer.

6 
1 2 
1 3 
1 4 
1 5 
1 6 

7 

提示

Since all nodes in the structure are connected to node $1$, we only need to buy one wire of length $2$ and three of length $1$, for a total cost of $2 * 2 + 1 * 1 + 1 * 1 + 1 * 1 = 7$.

Test data worth at least $50\%$ of the points will have $N \leq 2,000$.