Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Range Diameter Sum

time limit per test

7 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputYou are given a tree with $$$n$$$ vertices numbered $$$1, \ldots, n$$$. A tree is a connected simple graph without cycles.

Let $$$\mathrm{dist}(u, v)$$$ be the number of edges in the unique simple path connecting vertices $$$u$$$ and $$$v$$$.

Let $$$\mathrm{diam}(l, r) = \max \mathrm{dist}(u, v)$$$ over all pairs $$$u, v$$$ such that $$$l \leq u, v \leq r$$$.

Compute $$$\sum_{1 \leq l \leq r \leq n} \mathrm{diam}(l, r)$$$.

Input

The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the number of vertices in the tree.

The next $$$n - 1$$$ lines describe the tree edges. Each of these lines contains two integers $$$u, v$$$ ($$$1 \leq u, v \leq n$$$) — endpoint indices of the respective tree edge. It is guaranteed that the edge list indeed describes a tree.

Output

Print a single integer — $$$\sum_{1 \leq l \leq r \leq n} \mathrm{diam}(l, r)$$$.

Examples

Input

4 1 2 2 4 3 2

Output

10

Input

10 1 8 2 9 5 6 4 8 4 2 7 9 3 6 10 4 3 9

Output

224

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/23/2021 21:21:41 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|