Centroid Sum After Edge Removal

You are given a tree S with n nodes numbered from 1 to n and n-1 undirected edges. Recall that a tree of size n consists of n nodes and n-1 edges, and there is exactly one simple path between any two distinct nodes. Removing a node (and its incident edges) splits the tree into several disconnected subtrees, while removing an edge (keeping the nodes) splits the tree into exactly two subtrees.

For any tree of size n and any node c in the tree, c is called a centroid if, after removing c (and its incident edges), each of the resulting subtrees has at most \( \lfloor \frac{n}{2} \rfloor \) nodes. It is known that a tree with at least one node may have either 1 or 2 centroids.

You are given the tree S (with nodes numbered from 1 to n). For each edge \((u,v)\) in S, when that edge is removed, the tree splits into two subtrees: let \(S'_u\) be the subtree containing node u and \(S'_v\) be the subtree containing node v. Your task is to calculate the sum of the labels of the centroids in both subtrees for every edge removal. Formally, you must compute:

[ \sum_{(u,v) \in E} \left( \sum_{\substack{1 \le x \le n \ x \text{ is a centroid of } S'u}} x + \sum{\substack{1 \le y \le n \ y \text{ is a centroid of } S'_v}} y \right) ]

Help SmallSimple complete his homework!

inputFormat

The first line contains an integer n (1 ≤ n ≤ ...), the number of nodes in the tree.

Each of the next n-1 lines contains two integers u and v that denote an undirected edge between nodes u and v.

outputFormat

Output a single integer representing the total sum described in the problem statement.

sample

3
1 2
2 3

12