{"problem":{"name":"E. Roads","description":{"content":"The minister of transport of Byteland decided he needs to increase his popularity in order to aspire for presidency. Therefore, he wants to create a program that will maintain a system of transport vi","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":16384},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10100E"},"statements":[{"statement_type":"Markdown","content":"The minister of transport of Byteland decided he needs to increase his popularity in order to aspire for presidency. Therefore, he wants to create a program that will maintain a system of transport vital to the country.\n\nFor now he is interested in the most important N cities and he wants the system of transport to contain N - 1 roads in such a way that each city is connected to the capital (the city labeled with 1) and the total maintenance cost of the streets is as small as possible. Even though he found the optimal solution, in the future, M new roads will be built between the N cities so sometimes it might be better to modify the system of transport in order to have a minimum cost.\n\nThe first line of the input contains a single integer N. Each of the next N - 1 lines contains information about the initial system of transport. On line i there are two integers K and C, representing the city closest to capital that is connected to city i and the cost of maintenance of the street connecting these two cities. If the city is directly connected to the capital then K = 1.\n\nLine N + 1 contains an integer M. Each of the next M lines contains 3 integers X, Y and C, representing the fact that a new road is build between cities X and Y, having a maintenance cost equal to C.\n\nThe output should contain M lines. On line i print a single integer representing the minimum cost of the system of transportation after the first i roads have been built.\n\n## Input\n\nThe first line of the input contains a single integer N. Each of the next N - 1 lines contains information about the initial system of transport. On line i there are two integers K and C, representing the city closest to capital that is connected to city i and the cost of maintenance of the street connecting these two cities. If the city is directly connected to the capital then K = 1.Line N + 1 contains an integer M. Each of the next M lines contains 3 integers X, Y and C, representing the fact that a new road is build between cities X and Y, having a maintenance cost equal to C.\n\n## Output\n\nThe output should contain M lines. On line i print a single integer representing the minimum cost of the system of transportation after the first i roads have been built.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of cities, with city $ 1 $ as the capital.  \nLet $ T = (V, E_{\\text{init}}) $ be the initial tree with $ V = \\{1, 2, \\dots, N\\} $ and $ |E_{\\text{init}}| = N-1 $, where each edge $ (k, i) \\in E_{\\text{init}} $ (for $ i = 2, \\dots, N $) connects city $ i $ to its parent $ k $ (with $ k=1 $ if directly connected to the capital) and has weight $ C $.  \n\nLet $ M \\in \\mathbb{Z}^+ $ be the number of new roads.  \nLet $ R = \\{(x_j, y_j, c_j) \\mid j \\in \\{1, \\dots, M\\}\\} $ be the sequence of new edges, each with endpoints $ x_j, y_j \\in V $ and weight $ c_j \\in \\mathbb{R}^+ $.\n\n**Constraints**  \n1. $ 2 \\le N \\le 10^5 $  \n2. $ 1 \\le M \\le 10^5 $  \n3. For each initial edge $ (k, i, C) $: $ 1 \\le k < i \\le N $, $ 1 \\le C \\le 10^9 $  \n4. For each new edge $ (x_j, y_j, c_j) $: $ 1 \\le x_j, y_j \\le N $, $ x_j \\ne y_j $, $ 1 \\le c_j \\le 10^9 $\n\n**Objective**  \nAfter each new road $ j \\in \\{1, \\dots, M\\} $ is added to the graph, let $ G_j = (V, E_{\\text{init}} \\cup \\{(x_1, y_1, c_1), \\dots, (x_j, y_j, c_j)\\}) $.  \nCompute the minimum spanning tree (MST) cost of $ G_j $, and output it on line $ j $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10100E","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}