Tree Weight Sum via Farthest Paths

You are given a tree with \(n\) nodes. The tree represents a simplified complex network of \(n\) locations. For each vertex \(u\), consider the set of vertices that are the farthest from \(u\) in the tree. Let these vertices be \(v_1, v_2, \dots, v_k\). For each such vertex \(v_i\), increment by 1 the weight of every vertex on the unique simple path from \(u\) to \(v_i\) (both endpoints inclusive).

After carrying out this procedure starting from every vertex, output the total sum of the weights of all vertices.

Observation: In a tree, the farthest vertex from any node \(u\) is always one of the endpoints of the tree's diameter. Let these endpoints be \(A\) and \(B\). Then for every node \(u\), if we define \(d_A(u)=\)distance from \(u\) to \(A\) and \(d_B(u)=\)distance from \(u\) to \(B\), the contribution from vertex \(u\) is:

• If \(d_A(u) > d_B(u)\), then add \(d_A(u)+1\).
• If \(d_B(u) > d_A(u)\), then add \(d_B(u)+1\).
• If \(d_A(u) = d_B(u)\), then add \(\bigl(d_A(u)+1\bigr) + \bigl(d_B(u)+1\bigr) = d_A(u)+d_B(u)+2\).

Your task is to compute this total sum.

inputFormat

The first line contains an integer \(n\) (number of nodes). The next \(n-1\) lines each contain two integers \(u\) and \(v\) denoting an edge between nodes \(u\) and \(v\) (1-indexed).

outputFormat

Output a single integer representing the sum of weights of all vertices after processing all vertices.

sample

3
1 2
2 3

10