Problem I
Perfect Date
Hori-san and Miyamura-kun are high-school lovers with a special kind of chemistry any modern day couple would dream for. Their ability to understand each other on a deeper level better than anyone else is something only they can understand. Just like any blossoming youthful couple, they want to take the relationship one step further. Recently, there has been a new attraction in Kyoto called Matchmake!, an dating initiative by the Japanese Government to encourage more couples to get married and have children due to the declining birthrate.
The way Matchmake! works is simple: There is a plot of land modelled as a tree. This tree contains $N$ vertices and $N - 1$ edges. Furthermore, there is a parcel located at every vertex and at any point in time, each participating person/team can only carry one parcel at any point in time. Next, Hori and Miyamura will attempt to explore this tree.
They first pick an arbitrary vertex $i$ where $i \in {1,2,\ldots ,N}$ as a fixed deposit point for the parcels. The participating team will then go to another vertex, pick up its parcel and drop it off at $v_{i}$. They will repeat this process until all parcels have been dropped off.
To their horror, Matchmake! has one more twist. It is given that the distances between $2$ vertices is the cube of the sum of edge weights between them. Help Hori and Miyamura calculate the minimum total distance travelled, so that they can have the most memorable date ever.
Input
The first line contains an integer, $1 \le N \le 25\, 000$, the number of vertices of the tree.
The next $N - 1$ lines contain the edges, each on one line. Each edge is given in the form $u\, v\, w$ where $u,v$ are the $2$ endpoints of an edge ($1 \le u,v \le N$) and $w$ is the weight of an edge ($1 \le w \le 2$). The edges can be traversed in both directions.
Output
Print the answer on $1$ line, the minimum distance travelled by Hori and Miyamura. The answer is guaranteed to fit within a $64$-bit signed integer.
Explanation of Sample Input 2
Pick vertex $1$ as the fixed point.
-
Distance from $1 \rightarrow 2 = 1^{3} * 2 = 2$.
-
Distance from $1 \rightarrow 3 = 1^{3} * 2 = 2$.
-
Distance from $1 \rightarrow 4 = 2^{3} * 2 = 16$.
-
Distance from $1 \rightarrow 5 = 2^{3} * 2 = 16$.
Total distance travelled: $2 + 2 + 16 + 16 = 36$
| Sample Input 1 | Sample Output 1 |
|---|---|
4 1 2 1 1 3 1 1 4 1 |
6 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 1 2 1 1 3 1 2 4 1 3 5 1 |
36 |
