問題一覧 > 通常問題

No.922 東北きりきざむたん

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 80
作問者 : polylogKpolylogK / テスター : lumc_lumc_
10 ProblemId : 3420 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-11-08 23:58:18

数式が表示されない不具合が発生している場合は次の対応をお願いします.

https://twitter.com/yukicoder/status/1191757446596812800?s=20

問題文

東北地方の交通網は $N$ 個の都市と $N - 1$ 個の道路で表され,どの道路も長さは $1$ です.どの都市からどの都市へも道路を辿ることで移動が可能です.
また,マキさんには $Q$ 個の移動予定があり,$i$ 番目の移動予定では都市 $a_i$ から都市 $b_i$ へ移動するつもりです.
ところがある日、きりたんが東北地方のいくつかの道路を切断し,東北地方はいくつかの連結成分に分断されました.そのため,達成することが出来なくなった移動予定が発生してしまいました.
切断されていない道路は $M$ 個存在し,$i$ 番目の道路は都市 $u_i$ と都市 $v_i$ を相互に結んでいます.(追記しました)
そこでイタコさんはマキさんがすべての移動予定を達成できるように,各連結成分について高々一つの都市に空港を設置しようと考えました.空港から空港へは一瞬で移動できます(距離 $0$).
イタコさんが最適に空港を設置した時,マキさんがすべての移動予定を達成するために移動する距離の総和の最小値を求めてください。

入力

$N\ M\ Q$
$u_1\ v_1$
$\vdots$
$u_M\ v_M$
$a_1\ b_1$
$\vdots$
$a_Q\ b_Q$
  • $2 \le N \le 10^5$
  • $0 \le M \le N - 1$
  • $1 \le Q \le 10^5$
  • $1 \le u_i, v_i \le N$
    • $u_i \neq v_i$
    • $(u_i, v_i) = (u_j, v_j) \Leftrightarrow i = j$
  • $1 \le a_i, b_i \le N$
    • $a_i \neq b_i$
  • 入力はすべて整数.

出力

移動距離の総和の最小値を整数で一行に出力してください.

サンプル

サンプル1
入力
9 7 3
1 2
1 3
2 4
5 6
5 7
6 8
6 9
2 3
3 5
8 4
出力
7

例えば,頂点 $1$, $6$ を空港にすることで達成できます.

サンプル2
入力
7 6 3
1 2
1 3
2 4
2 5
3 6
3 7
4 7
5 6
2 3
出力
10

きりたんは道路を切断しませんでした.

サンプル3
入力
3 0 3
1 2
2 3
3 1
出力
0

きりたんは全ての道路を切断してしまいました.

サンプル4
入力
10 5 7
3 7
10 4
1 4
4 8
5 8
10 1
6 9
5 9
9 2
6 9
7 6
10 1
出力
4

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。