{"problem":{"name":"E. Minimum Spanning Tree","description":{"content":"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","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10222E"},"statements":[{"statement_type":"Markdown","content":"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$.\n\nPrecisely speaking, for an undirected weighted graph $G$ without loops or multiple edges, its line graph $L (G)$ is a graph such that: \n\nA 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.\n\nGiven a tree $G$, please write a program to find the minimum spanning tree of $L (G)$.\n\nThe first line of the input contains an integer $T (1 <= T <= 1000)$, denoting the number of test cases.\n\nIn each test case, there is one integer $n (2 <= n <= 100000)$ in the first line, denoting the number of vertices of $G$.\n\nFor the next $n -1$ lines, each line contains three integers $u, v, w (1 <= u, v <= n, u eq.not v, 1 <= w <= 10^9)$, denoting a bidirectional edge between vertex $u$ and $v$ with weight $w$.\n\nIt is guaranteed that $sum n <= 10^6$.\n\nFor each test case, print a single line containing an integer, denoting the sum of all the edges' weight of $M S T (L (G))$.\n\n## Input\n\nThe first line of the input contains an integer $T (1 <= T <= 1000)$, denoting the number of test cases.In each test case, there is one integer $n (2 <= n <= 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 <= u, v <= n, u eq.not v, 1 <= w <= 10^9)$, denoting a bidirectional edge between vertex $u$ and $v$ with weight $w$.It is guaranteed that $sum n <= 10^6$.\n\n## Output\n\nFor each test case, print a single line containing an integer, denoting the sum of all the edges' weight of $M S T (L (G))$.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ n_k \\in \\mathbb{Z} $ denote the number of insertions.  \n- Let $ A_k = (a_{k,1}, a_{k,2}, \\dots, a_{k,n_k}) $ be a permutation of $ \\{1, 2, \\dots, n_k\\} $, representing the sequence of values inserted into an initially empty 2-3-4 tree.\n\n**Constraints**  \n1. $ 1 \\le T \\le 50 $  \n2. For each $ k \\in \\{1, \\dots, T\\} $:  \n   - $ 1 \\le n_k \\le 5000 $  \n   - $ A_k $ is a permutation of $ \\{1, 2, \\dots, n_k\\} $\n\n**Objective**  \nAfter inserting all elements of $ A_k $ into an initially empty 2-3-4 tree, output the tree structure in pre-order traversal, where each node is printed as a line containing its data elements in ascending order.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10222E","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}