{"problem":{"name":"F. Mobile Phone Network","description":{"content":"You are managing a mobile phone network, and want to offer competitive prices to connect a network. The network has $n$ nodes. Your competitor has already offered some connections between some nodes","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF1023F"},"statements":[{"statement_type":"Markdown","content":"You are managing a mobile phone network, and want to offer competitive prices to connect a network.\n\nThe network has $n$ nodes.\n\nYour competitor has already offered some connections between some nodes, with some fixed prices. These connections are bidirectional. There are initially $m$ connections the competitor is offering. The $i$\\-th connection your competitor is offering will connect nodes $fa_i$ and $fb_i$ and costs $fw_i$.\n\nYou have a list of $k$ connections that you want to offer. It is guaranteed that this set of connection does not form any cycle. The $j$\\-th of these connections will connect nodes $ga_j$ and $gb_j$. These connections are also bidirectional. The cost of these connections have not been decided yet.\n\nYou can set the prices of these connections to any arbitrary integer value. These prices are set independently for each connection. After setting the prices, the customer will choose such $n - 1$ connections that all nodes are connected in a single network and the total cost of chosen connections is minimum possible. If there are multiple ways to choose such networks, the customer will choose an arbitrary one that also maximizes the number of your connections in it.\n\nYou want to set prices in such a way such that **all** your $k$ connections are chosen by the customer, and the sum of prices of your connections is maximized.\n\nPrint the maximum profit you can achieve, or $-1$ if it is unbounded.\n\n## Input\n\nThe first line of input will contain three integers $n$, $k$ and $m$ ($1 \\leq n, k, m \\leq 5 \\cdot 10^5, k \\leq n-1$), the number of nodes, the number of your connections, and the number of competitor connections, respectively.\n\nThe next $k$ lines contain two integers $ga_i$ and $gb_i$ ($1 \\leq ga_i, gb_i \\leq n$, $ga_i \\not= gb_i$), representing one of your connections between nodes $ga_i$ and $gb_i$. Your set of connections is guaranteed to be acyclic.\n\nThe next $m$ lines contain three integers each, $fa_i$, $fb_i$ and $fw_i$ ($1 \\leq fa_i, fb_i \\leq n$, $fa_i \\not= fb_i$, $1 \\leq fw_i \\leq 10^9$), denoting one of your competitor's connections between nodes $fa_i$ and $fb_i$ with cost $fw_i$. None of these connections connects a node to itself, and no pair of these connections connect the same pair of nodes. In addition, these connections are given by non-decreasing order of cost (that is, $fw_{i-1} \\leq fw_i$ for all valid $i$).\n\nNote that there may be some connections that appear in both your set and your competitor's set (though no connection will appear twice in one of this sets).\n\nIt is guaranteed that the union of all of your connections and your competitor's connections form a connected network.\n\n## Output\n\nPrint a single integer, the maximum possible profit you can achieve if you set the prices on your connections appropriately. If the profit is unbounded, print $-1$.\n\n[samples]\n\n## Note\n\nIn the first sample, it's optimal to give connection $1-3$ cost $3$, connection $1-2$ cost $3$, and connection $3-4$ cost $8$. In this case, the cheapest connected network has cost $14$, and the customer will choose one that chooses all of your connections.\n\nIn the second sample, as long as your first connection costs $30$ or less, the customer chooses both your connections no matter what is the cost of the second connection, so you can get unbounded profit in this case.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"你正在管理一个移动电话网络，希望提供有竞争力的价格来构建网络。\n\n网络中有 $n$ 个节点。\n\n你的竞争对手已经提供了一些节点之间的连接，价格固定。这些连接是双向的。最初，竞争对手提供了 $m$ 条连接。竞争对手提供的第 $i$ 条连接将连接节点 $f a_i$ 和 $f b_i$，费用为 $f w_i$。\n\n你有一份包含 $k$ 条连接的列表，你希望提供这些连接。保证这组连接不形成任何环。第 $j$ 条这样的连接将连接节点 $g a_j$ 和 $g b_j$。这些连接也是双向的，但它们的价格尚未确定。\n\n你可以将这些连接的价格设置为任意整数值。每条连接的价格独立设置。设置价格后，客户会选择 $n - 1$ 条连接，使得所有节点构成一个连通网络，且所选连接的总成本最小。如果存在多种这样的选择方式，客户会选择其中一种，使得你提供的连接数量最大化。\n\n你希望设置价格，使得你的全部 $k$ 条连接都被客户选中，并且你提供的连接的总价格最大化。\n\n请输出你能获得的最大利润，如果利润无界，则输出 $-1$。\n\n输入的第一行包含三个整数 $n$、$k$ 和 $m$（$1 lt.eq n, k, m lt.eq 5 dot.op 10^5, k lt.eq n -1$），分别表示节点数、你的连接数和竞争对手的连接数。\n\n接下来的 $k$ 行，每行包含两个整数 $g a_i$ 和 $g b_i$（$1 lt.eq g a_i, g b_i lt.eq n$，$g a_i not = g b_i$），表示你的一条连接，连接节点 $g a_i$ 和 $g b_i$。你的连接集合保证无环。\n\n接下来的 $m$ 行，每行包含三个整数 $f a_i$、$f b_i$ 和 $f w_i$（$1 lt.eq f a_i, f b_i lt.eq n$，$f a_i not = f b_i$，$1 lt.eq f w_i lt.eq 10^9$），表示竞争对手的一条连接，连接节点 $f a_i$ 和 $f b_i$，费用为 $f w_i$。这些连接不会连接节点到自身，且没有两条连接连接相同的节点对。此外，这些连接按费用非降序给出（即对所有合法的 $i$，有 $f w_(i -1) lt.eq f w_i$）。\n\n注意，可能存在一些连接同时出现在你的集合和竞争对手的集合中（但每个集合内部不会重复出现同一条连接）。\n\n保证你和竞争对手的所有连接的并集构成一个连通网络。\n\n输出一个整数，表示当你适当设置你的连接价格时，所能获得的最大可能利润。如果利润无界，请输出 $-1$。\n\n在第一个样例中，最优方案是将连接 $1 -3$ 设为成本 $3$，连接 $1 -2$ 设为成本 $3$，连接 $3 -4$ 设为成本 $8$。此时，最便宜的连通网络总成本为 $14$，客户会选择包含你所有连接的方案。\n\n在第二个样例中，只要你的第一条连接成本不超过 $30$，无论第二条连接的成本是多少，客户都会选择你的两条连接，因此你可以获得无界的利润。\n\n## Input\n\n输入的第一行包含三个整数 $n$、$k$ 和 $m$（$1 lt.eq n, k, m lt.eq 5 dot.op 10^5, k lt.eq n -1$），分别表示节点数、你的连接数和竞争对手的连接数。接下来的 $k$ 行，每行包含两个整数 $g a_i$ 和 $g b_i$（$1 lt.eq g a_i, g b_i lt.eq n$，$g a_i not = g b_i$），表示你的一条连接，连接节点 $g a_i$ 和 $g b_i$。你的连接集合保证无环。接下来的 $m$ 行，每行包含三个整数 $f a_i$、$f b_i$ 和 $f w_i$（$1 lt.eq f a_i, f b_i lt.eq n$，$f a_i not = f b_i$，$1 lt.eq f w_i lt.eq 10^9$），表示竞争对手的一条连接，连接节点 $f a_i$ 和 $f b_i$，费用为 $f w_i$。这些连接不会连接节点到自身，且没有两条连接连接相同的节点对。此外，这些连接按费用非降序给出（即对所有合法的 $i$，有 $f w_(i -1) lt.eq f w_i$）。注意，可能存在一些连接同时出现在你的集合和竞争对手的集合中（但每个集合内部不会重复出现同一条连接）。保证你和竞争对手的所有连接的并集构成一个连通网络。\n\n## Output\n\n输出一个整数，表示当你适当设置你的连接价格时，所能获得的最大可能利润。如果利润无界，请输出 $-1$。\n\n[samples]\n\n## Note\n\n在第一个样例中，最优方案是将连接 $1 -3$ 设为成本 $3$，连接 $1 -2$ 设为成本 $3$，连接 $3 -4$ 设为成本 $8$。此时，最便宜的连通网络总成本为 $14$，客户会选择包含你所有连接的方案。\n\n在第二个样例中，只要你的第一条连接成本不超过 $30$，无论第二条连接的成本是多少，客户都会选择你的两条连接，因此你可以获得无界的利润。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ G = (V, E) $ be a connected undirected graph with $ |V| = n $ nodes.  \nLet $ E_c \\subseteq E $ be the set of $ m $ competitor connections, each $ e \\in E_c $ has fixed cost $ w_e \\in \\mathbb{Z}^+ $.  \nLet $ E_p \\subseteq E $ be the set of $ k $ your proposed connections, initially with unknown prices, and $ E_p $ is acyclic (i.e., a forest).  \nLet $ E_{\\text{total}} = E_c \\cup E_p $, and it is guaranteed that $ G $ is connected via $ E_{\\text{total}} $.  \n\nLet $ x_j \\in \\mathbb{Z} $ denote the price assigned to the $ j $-th connection in $ E_p $, for $ j = 1, \\dots, k $.  \n\n**Constraints**  \n1. $ 1 \\le n, k, m \\le 5 \\cdot 10^5 $, $ k \\le n - 1 $  \n2. $ E_p $ is acyclic (no cycles)  \n3. Competitor edges are given in non-decreasing order of cost: $ w_i \\le w_{i+1} $ for all $ i \\in \\{1, \\dots, m-1\\} $  \n4. All edges in $ E_c $ and $ E_p $ are distinct within their own sets (no duplicates), but $ E_c \\cap E_p $ may be non-empty.  \n5. The graph $ (V, E_c \\cup E_p) $ is connected.  \n\n**Objective**  \nAssign prices $ x_1, \\dots, x_k \\in \\mathbb{Z} $ to edges in $ E_p $ such that:  \n- The customer selects a minimum-cost spanning tree (MST) of $ (V, E_c \\cup E_p) $,  \n- Among all MSTs of minimum total cost, the customer chooses one that **maximizes the number of your edges** $ E_p $,  \n- **Your goal**: Ensure **all** $ k $ edges in $ E_p $ are included in the chosen MST,  \n- **Maximize** the total profit: $ \\sum_{j=1}^k x_j $,  \n\nIf such an assignment exists and the profit is unbounded, output $ -1 $.  \nOtherwise, output the maximum possible profit.  \n\n**Key Insight**  \nFor each $ e \\in E_p $, its price $ x_e $ must be set so that it is **strictly cheaper than any alternative path** in $ E_c $ that could replace it in the MST — but only considering the constraints imposed by the MST algorithm and the tie-breaking rule (favoring your edges).  \n\nSpecifically, for each $ e \\in E_p $, define the **critical threshold** $ t_e $: the minimum cost such that if $ x_e > t_e $, then there exists a competing path in $ E_c $ that can replace $ e $ in the MST without increasing total cost, violating the requirement that all your edges are selected.  \n\nThe maximum possible $ x_e $ is $ t_e $, and the total profit is $ \\sum_{e \\in E_p} t_e $.  \n\nIf for any $ e \\in E_p $, no such finite $ t_e $ exists (i.e., no competing path can replace it regardless of price), then profit is unbounded → output $ -1 $.  \n\n**Formal Objective**  \nLet $ \\mathcal{T} $ be the set of all spanning trees of $ (V, E_c \\cup E_p) $.  \nFor each $ e \\in E_p $, define:  \n$$\nt_e = \\min \\left\\{ \\max_{f \\in P} w_f \\,\\middle|\\, P \\text{ is a path in } E_c \\cup (E_p \\setminus \\{e\\}) \\text{ connecting the endpoints of } e \\right\\}\n$$  \nThen, to ensure $ e $ is included in **every** MST that maximizes your edge count, we must set:  \n$$\nx_e \\le t_e\n$$  \nand to maximize profit, set $ x_e = t_e $.  \n\nIf for any $ e \\in E_p $, the set of such paths $ P $ is empty (i.e., $ e $ is a bridge in $ (V, E_c \\cup E_p \\setminus \\{e\\}) $), then $ t_e = \\infty $ → profit unbounded → output $ -1 $.  \n\nOtherwise, the maximum profit is:  \n$$\n\\sum_{e \\in E_p} t_e\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF1023F","tags":["dfs and similar","dsu","graphs","trees"],"sample_group":[["4 3 6\n1 2\n3 4\n1 3\n2 3 3\n3 1 4\n1 2 4\n4 2 8\n4 3 8\n4 1 10","14"],["3 2 1\n1 2\n2 3\n1 2 30","\\-1"],["4 3 3\n1 2\n1 3\n1 4\n4 1 1000000000\n4 2 1000000000\n4 3 1000000000","3000000000"]],"created_at":"2026-03-03 11:00:39"}}