406033: GYM102220 E Minimum Spanning Tree

In the mathematical discipline of graph theory, the line graph of a simple undirected weighted graph $$$G$$$ is another simple undirected weighted graph $$$L(G)$$$ that represents the adjacency between every two edges in $$$G$$$.

Precisely speaking, for an undirected weighted graph $$$G$$$ without loops or multiple edges, its line graph $$$L(G)$$$ is a graph such that:

• Each vertex of $$$L(G)$$$ represents an edge of $$$G$$$.
• Two vertices of $$$L(G)$$$ are adjacent if and only if their corresponding edges share a common endpoint in $$$G$$$, and the weight of such edge between this two vertices is the sum of their corresponding edges' weight.

A minimum spanning tree(MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible.

Given a tree $$$G$$$, please write a program to find the minimum spanning tree of $$$L(G)$$$.

The first line of the input contains an integer $$$T(1\leq T\leq 1000)$$$, denoting the number of test cases.

In each test case, there is one integer $$$n(2\leq n\leq 100000)$$$ in the first line, denoting the number of vertices of $$$G$$$.

For the next $$$n-1$$$ lines, each line contains three integers $$$u,v,w(1\leq u,v\leq n,u\neq v,1\leq w\leq 10^9)$$$, denoting a bidirectional edge between vertex $$$u$$$ and $$$v$$$ with weight $$$w$$$.

It is guaranteed that $$$\sum n\leq 10^6$$$.

For each test case, print a single line containing an integer, denoting the sum of all the edges' weight of $$$MST(L(G))$$$.

2
4
1 2 1
2 3 2
3 4 3
4
1 2 1
1 3 1
1 4 1

8
4