{"problem":{"name":"D. 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":"CF951D"},"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 $ n, k, m \\in \\mathbb{Z}^+ $ denote the number of nodes, your connections, and competitor connections, respectively.  \nLet $ E_y = \\{ e_j = (g a_j, g b_j) \\mid j \\in \\{1, \\dots, k\\} \\} $ be the set of your $ k $ bidirectional connections, forming a forest (acyclic).  \nLet $ E_c = \\{ (f a_i, f b_i, f w_i) \\mid i \\in \\{1, \\dots, m\\} \\} $ be the set of competitor connections, each with fixed cost $ f w_i $, given in non-decreasing order of cost.  \nLet $ G = (V, E_y \\cup E_c) $ be the full graph, with $ |V| = n $, and it is guaranteed that $ G $ is connected.\n\nLet $ p_j \\in \\mathbb{Z} $ be the price assigned to your connection $ e_j \\in E_y $.  \nLet $ P = (p_1, \\dots, p_k) \\in \\mathbb{Z}^k $ be the price vector for your connections.\n\n**Constraints**  \n1. $ 1 \\le n, k, m \\le 5 \\cdot 10^5 $, $ k \\le n - 1 $  \n2. $ E_y $ is acyclic.  \n3. $ E_c $ has no self-loops or duplicate edges.  \n4. $ f w_i \\le f w_{i+1} $ for all $ i \\in \\{1, \\dots, m-1\\} $.  \n5. $ G = (V, E_y \\cup E_c) $ is connected.  \n6. The customer selects a minimum-cost spanning tree (MST) of $ G $, breaking ties by maximizing the number of your connections included.\n\n**Objective**  \nFind the maximum possible value of $ \\sum_{j=1}^k p_j $, over all $ P \\in \\mathbb{Z}^k $, such that **every** edge in $ E_y $ is included in **some** MST selected by the customer under the tie-breaking rule.  \nIf no such finite maximum exists (i.e., profit is unbounded), output $ -1 $.\n\n**Key Condition for Inclusion**  \nFor each $ e_j \\in E_y $, let $ C_j $ be the fundamental cycle formed by adding $ e_j $ to the MST of $ G \\setminus \\{e_j\\} $ using only edges from $ E_c $.  \nThen, to ensure $ e_j $ is included in *some* MST (and ultimately all $ E_y $ are included), we require:  \n$$\np_j \\le \\min_{e \\in C_j \\cap E_c} w(e)\n$$  \nMoreover, to ensure that **all** $ k $ your edges are selected under the tie-breaking rule (i.e., when multiple MSTs exist, the one with maximum your edges is chosen), we must have:  \n$$\np_j \\le \\min_{e \\in \\text{min-cut}(e_j \\text{ in } G \\setminus E_y)} w(e)\n$$  \nBut more precisely: for each $ e_j \\in E_y $, define $ \\lambda_j = \\min \\{ w(e) \\mid e \\in E_c \\text{ and } e \\text{ forms a cycle with } e_j \\text{ in } E_y \\cup E_c \\} $.  \nThen, for $ e_j $ to be included in **every** MST (or at least, in the one chosen under tie-breaking), we must have:  \n$$\np_j \\le \\lambda_j\n$$  \nAnd to **maximize** your profit, set $ p_j = \\lambda_j $ for all $ j \\in \\{1, \\dots, k\\} $.\n\n**Unboundedness Condition**  \nIf for any $ e_j \\in E_y $, there is **no** competitor edge that forms a cycle with $ e_j $ (i.e., $ \\lambda_j = \\infty $), then $ p_j $ can be set arbitrarily large → profit unbounded → output $ -1 $.\n\n**Final Objective**  \nCompute:\n$$\n\\max \\sum_{j=1}^k p_j = \\sum_{j=1}^k \\lambda_j\n$$\nwhere $ \\lambda_j = \\min \\{ w(e) \\mid e \\in E_c \\text{ and } e \\text{ lies on the unique cycle in } E_y \\cup \\{e\\} \\} $,  \nand if $ \\exists j $ such that $ \\lambda_j = \\infty $, output $ -1 $.\n\nThus:\n\n**Objective**  \n$$\n\\boxed{\n\\begin{cases}\n\\displaystyle \\sum_{j=1}^k \\lambda_j & \\text{if } \\forall j, \\lambda_j < \\infty \\\\\n-1 & \\text{otherwise}\n\\end{cases}\n}\n\\quad \\text{where} \\quad\n\\lambda_j = \\min \\left\\{ w(e) \\mid e \\in E_c, \\; e \\text{ closes a cycle with } e_j \\text{ in } E_y \\cup E_c \\right\\}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF951D","tags":[],"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"}}