Sum of Complement Graph Shortest Paths on a Tree

Given a tree \(T\) with \(n\) nodes and weighted edges, where the nodes are a permutation of \([1,n]\). Let \(T\) have \(n-1\) edges. Define \(\text{G}\) to be the complement graph of \(T\) (i.e. \(\text{G}\) contains all the \(\binom{n}{2}\) pairs except the tree edges).

For every edge \((x,y)\) in \(\text{G}\), its weight is defined as the sum of weights along the unique simple path from \(x\) to \(y\) in \(T\); that is, if \(P_{xy}\) is the unique simple path in \(T\) then its weight is \[ w(x,y)=\sum_{e\in P_{xy}} w_e. \]

For any two distinct nodes \(x\) and \(y\), let \(dis(x,y)\) denote the length of the shortest path between them in \(\text{G}\). If \(x\) and \(y\) are disconnected in \(\text{G}\) then we define \(dis(x,y)=0\). Note that if \(x\) and \(y\) are adjacent in \(T\) then the direct edge \((x,y)\) is missing in \(\text{G}\) and thus \(dis(x,y)\) must be computed via a two or more hop path if one exists.

Your task is to compute \[ S = \sum_{1 \le i < j \le n} dis(i,j). \]

Observation and Hints:

• For two nodes \(i\) and \(j\) that are not directly connected in \(T\), there is a direct edge in \(\text{G}\) with weight equal to the distance \(d_T(i,j)\) in \(T\). Hence \(dis(i,j)=d_T(i,j)\).
• For a pair \(i,j\) where \((i,j)\) is an edge in \(T\) (with weight \(w\)), the direct edge is missing in \(\text{G}\). In this case, one must choose an intermediate vertex \(k\) (with \(k\neq i,j\)) such that both edges \((i,k)\) and \((j,k)\) exist in \(\text{G}\) and
  \(dis(i,j)=w+2\,d_T(i,k)\) (if \(k\) lies in the connected component of \(T\setminus\{(i,j)\}\) containing \(i\)) or similarly from \(j\)'s side. If no such \(k\) exists the contribution is taken as 0.
• The overall answer can be expressed as \[ \text{Ans} = \Bigl(\sum_{1\le i<j\le n} d_T(i,j)\Bigr) - \Bigl(\sum_{(i,j)\in T} w_{ij}\Bigr) + \sum_{(i,j)\in T} f(i,j), \] where for each edge \((i,j)\) in \(T\) with weight \(w_{ij}\), \[ f(i,j)=\begin{cases} w_{ij}+2\min\{\delta_i,\delta_j\} & \text{if there exists some candidate vertex}\\[1mm] 0 & \text{otherwise,} \end{cases} \] and \(\delta_i\) is the minimum tree distance from \(i\) to any vertex in the corresponding connected component (after removing the edge \((i,j)\)) such that the candidate vertex is not directly adjacent to \(i\) in \(T\). (A similar definition holds for \(\delta_j\)).

Input Format:

• The first line contains an integer \(n\) (the number of nodes).
• The next \(n-1\) lines each contain three integers \(u\), \(v\) and \(w\), denoting an edge between nodes \(u\) and \(v\) with weight \(w\) in \(T\).

Output Format:

• Output a single number, the sum \(S=\sum_{1\le i<j\le n} dis(i,j)\).

Note: It is guaranteed that the input forms a tree and that the nodes are labeled with a permutation of \(\{1,2,\dots,n\}\).

inputFormat

The input begins with an integer \(n\), the number of nodes. Then, there are \(n-1\) lines. Each of these lines contains three integers \(u\), \(v\), and \(w\) representing an edge between nodes \(u\) and \(v\) with weight \(w\) in the tree \(T\).

outputFormat

Output a single integer representing the sum \(S=\sum_{1\le i<j\le n} dis(i,j)\) as defined above.

sample

3
1 2 3
2 3 4

7