Hiking Mania

Time limit2sMemory limit512 MB

Summary

Given a tree rooted at node 1, sum over all pairs (i,j) the number of distinct edges on the shortest i-to-j walk forced to pass through the root.

Level: Medium7 of 10
Topics: Tree, DFS, Combinatorics, Math
Solved: No attempts yet

Problem

There is a hiking trail on the mountain behind the neighborhood. The trail consists of $N$ small huts connected by $N-1$ footpaths. A footpath connects two huts in both directions, and its length is 1. From any hut, you can reach every other hut by following footpaths. The huts are numbered from 1 to $N$ , and hut 1 is at the summit. Every footpath on the shortest path from hut 1 to any other hut always goes downhill.

Cheolsu is a hiking maniac. Whenever Cheolsu travels from one hut to another, he always follows the shortest path that passes through the summit. The diversity of such a path is defined as the number of footpaths it contains. Note that a footpath traversed more than once is counted only once.

The figure below shows one possible situation. Hut 1 is at the summit, and huts 3 and 4 are connected by a footpath.

The figure below shows the shortest path from hut 2 to hut 7.

The figure below shows the shortest path from hut 2 to hut 7 that passes through the summit.

Given the structure of the trail as input, write a program that computes, for every pair $(i, j)$ with $1 \le i < j \le N$ , the total sum of the diversity of the path Cheolsu takes from hut $i$ to hut $j$ .

Input

The first line contains $N$ . The next $N-1$ lines each contain two hut numbers separated by a single space. This means the two huts are connected by a footpath.

Output

Print the answer to the problem on the first line.

Constraints

$2 \le N \le 300\,000$

Examples2

Example 1
Input
```
3
1 2
2 3
```
Expected output
```
5
```
Example 2
Input
```
8
6 2
7 5
3 4
5 6
1 5
4 1
8 6
```
Expected output
```
84
```