题目描述

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 <= N <= 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 <= A <= N; 1 <= B <= N; A != 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!

Test data worth at least 50% of the points will have N <= 2,000.

Partial feedback will be provided on your first 50 submissions to this problem.

TIME LIMIT: 2 seconds

MEMORY LIMIT: 64 MB

奶牛决定用电线焊接出一个特殊图形，这个图形是连通的，由N个点，N -1条边组成， 每条边的长度都是1。焊接所用的电线要从当地的商店里买。越长的电线越贵，一条长度为 L的电线售价为L^2 。 奶牛们已经学会了基本的焊接方法， 她们会把某条电线的一个端点焊接到另一条电线的 中间某个位置， 但她们没有学会如何把两条电线的端点直接焊接起来， 也没有学会怎么把电 线剪断。 告诉你奶牛准备焊接的图形，请告诉奶牛怎么焊接才能最节约材料费用。

输入格式

* Line 1: A single integer: N

* Lines 2..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.