English · Original
Chinese · Translation
Formal · Original
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, 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$.
You 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.
You 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.
You 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.
Print the maximum profit you can achieve, or $-1$ if it is unbounded.
## Input
The 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.
The 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.
The 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$).
Note 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).
It is guaranteed that the union of all of your connections and your competitor's connections form a connected network.
## Output
Print 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$.
[samples]
## Note
In 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.
In 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.
你正在管理一个移动电话网络，希望提供有竞争力的价格来构建网络。
网络中有 $n$ 个节点。
你的竞争对手已经提供了一些节点之间的连接，价格固定。这些连接是双向的。最初，竞争对手提供了 $m$ 条连接。竞争对手提供的第 $i$ 条连接将连接节点 $f a_i$ 和 $f b_i$，费用为 $f w_i$。
你有一份包含 $k$ 条连接的列表，你希望提供这些连接。保证这组连接不形成任何环。第 $j$ 条这样的连接将连接节点 $g a_j$ 和 $g b_j$。这些连接也是双向的，但它们的价格尚未确定。
你可以将这些连接的价格设置为任意整数值。每条连接的价格独立设置。设置价格后，客户会选择 $n - 1$ 条连接，使得所有节点构成一个连通网络，且所选连接的总成本最小。如果存在多种这样的选择方式，客户会选择其中一种，使得你提供的连接数量最大化。
你希望设置价格，使得你的全部 $k$ 条连接都被客户选中，并且你提供的连接的总价格最大化。
请输出你能获得的最大利润，如果利润无界，则输出 $-1$。
输入的第一行包含三个整数 $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$）。
注意，可能存在一些连接同时出现在你的集合和竞争对手的集合中（但每个集合内部不会重复出现同一条连接）。
保证你和竞争对手的所有连接的并集构成一个连通网络。
输出一个整数，表示当你适当设置你的连接价格时，所能获得的最大可能利润。如果利润无界，请输出 $-1$。
在第一个样例中，最优方案是将连接 $1 -3$ 设为成本 $3$，连接 $1 -2$ 设为成本 $3$，连接 $3 -4$ 设为成本 $8$。此时，最便宜的连通网络总成本为 $14$，客户会选择包含你所有连接的方案。
在第二个样例中，只要你的第一条连接成本不超过 $30$，无论第二条连接的成本是多少，客户都会选择你的两条连接，因此你可以获得无界的利润。
## Input
输入的第一行包含三个整数 $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$）。注意，可能存在一些连接同时出现在你的集合和竞争对手的集合中（但每个集合内部不会重复出现同一条连接）。保证你和竞争对手的所有连接的并集构成一个连通网络。
## Output
输出一个整数，表示当你适当设置你的连接价格时，所能获得的最大可能利润。如果利润无界，请输出 $-1$。
[samples]
## Note
在第一个样例中，最优方案是将连接 $1 -3$ 设为成本 $3$，连接 $1 -2$ 设为成本 $3$，连接 $3 -4$ 设为成本 $8$。此时，最便宜的连通网络总成本为 $14$，客户会选择包含你所有连接的方案。
在第二个样例中，只要你的第一条连接成本不超过 $30$，无论第二条连接的成本是多少，客户都会选择你的两条连接，因此你可以获得无界的利润。
**Definitions**
Let $ G = (V, E) $ be a connected undirected graph with $ |V| = n $ nodes.
Let $ E_c \subseteq E $ be the set of $ m $ competitor connections, each $ e \in E_c $ has fixed cost $ w_e \in \mathbb{Z}^+ $.
Let $ 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).
Let $ E_{\text{total}} = E_c \cup E_p $, and it is guaranteed that $ G $ is connected via $ E_{\text{total}} $.
Let $ x_j \in \mathbb{Z} $ denote the price assigned to the $ j $-th connection in $ E_p $, for $ j = 1, \dots, k $.
**Constraints**
1. $ 1 \le n, k, m \le 5 \cdot 10^5 $, $ k \le n - 1 $
2. $ E_p $ is acyclic (no cycles)
3. Competitor edges are given in non-decreasing order of cost: $ w_i \le w_{i+1} $ for all $ i \in \{1, \dots, m-1\} $
4. 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.
5. The graph $ (V, E_c \cup E_p) $ is connected.
**Objective**
Assign prices $ x_1, \dots, x_k \in \mathbb{Z} $ to edges in $ E_p $ such that:
- The customer selects a minimum-cost spanning tree (MST) of $ (V, E_c \cup E_p) $,
- Among all MSTs of minimum total cost, the customer chooses one that **maximizes the number of your edges** $ E_p $,
- **Your goal**: Ensure **all** $ k $ edges in $ E_p $ are included in the chosen MST,
- **Maximize** the total profit: $ \sum_{j=1}^k x_j $,
If such an assignment exists and the profit is unbounded, output $ -1 $.
Otherwise, output the maximum possible profit.
**Key Insight**
For 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).
Specifically, 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.
The maximum possible $ x_e $ is $ t_e $, and the total profit is $ \sum_{e \in E_p} t_e $.
If 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 $.
**Formal Objective**
Let $ \mathcal{T} $ be the set of all spanning trees of $ (V, E_c \cup E_p) $.
For each $ e \in E_p $, define:
$$
t_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\}
$$
Then, to ensure $ e $ is included in **every** MST that maximizes your edge count, we must set:
$$
x_e \le t_e
$$
and to maximize profit, set $ x_e = t_e $.
If 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 $.
Otherwise, the maximum profit is:
$$
\sum_{e \in E_p} t_e
$$
API Response (JSON)
{
"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...",
"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$ 条连接的列表，你希望提供这些连接。保证这组连接不形成任何环。第 $...",
"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...",
"is_translate": false,
"language": "Formal"
}
]
}