Codeforces ラウンド #250 (ディビジョン 1)B (ソート + ユニオン検索)_html/css_WEB-ITnose

B. 子供と動物園

テストごとの制限時間

2 秒

テストごとのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

もちろん私たちの子供は動物園を歩くのが好きです。動物園には n 個のエリアがあり、1 から n まで番号が付けられています。 i 番目のエリアには、ai 動物が含まれています。また、動物園内には m 個の道路があり、それぞれの道路が 2 つの異なるエリアを接続しています。当然動物園はつながっているので、道路を使えば他のエリアからでも動物園のどのエリアにも行くことができます

うちの子はとても賢いです。子供がエリア p からエリア q に行きたいと考えていると想像してください。まず、p から q までのすべての単純なルートを検討します。各ルートについて、子供はルートエリア内の動物の最小数に等しい数を書き留めます。書かれた数字の最大のものを f(p,?q) と表します。最後に、子供はルートの 1 つを選択し、値 f(p,?q) を書き留めます。

子供が動物園を訪れた後、次の質問について考えます。f(p,?q) の平均値はいくらですか? ?q) すべてのペア p,?q (p?≠?q)?彼の質問に答えられますか?

入力

最初の行には 2 つの整数 n と m (2?≤?n?≤?105; 0?≤?m?≤?105) が含まれています。 2 行目には n 個の整数が含まれています: a1,?a2,?...,?an (0?≤?ai?≤?105)。次に m 行をたどります。各行には 2 つの整数 xi と yi (1?≤?xi,?yi?≤?n; xi?≠?yi) が含まれており、領域 xi と yi の間の道路を示します。

すべての道路は双方向です。エリアの各ペアは、最大 1 つの道路で接続されています。

出力

実数を出力しますか?の値。

相対誤差または絶対誤差が 10?-?4 を超​​えない場合、答えは正しいとみなされます。

サンプル テスト

入力

4 310 20 30 401 32 34 3

出力

16.666667

入力

3 310 20 301 22 33 1

出力

13.333333

入力

7 840 20 10 30 20 50 401 22 33 44 55 66 71 45 7

出力

18.571429

注

最初のサンプルを考えてみましょう。考えられる状況は 12 個あります:

p?=?1,?q?=?3,?f(p,?q)?=?10.

p?=?2,?q?=?3,? f(p,?q)?=?20.

p?=?4,?q?=?3,?f(p,?q)?=?30.

p?=?1,?q ?=?2,?f(p,?q)?=?10.

p?=?2,?q?=?4,?f(p,?q)?=?20.

p? =?4,?q?=?1,?f(p,?q)?=?10.

別の 6 つのケースは上記と対称です。平均は です。

2 番目のサンプルを考えてみましょう。考えられる状況は 6 つあります:

p?=?1,?q?=?2,?f(p,?q)?=?10.

p?=?2,?q?=?3,? f(p,?q)?=?20.

p?=?1,?q?=?3,?f(p,?q)?=?10.

別の 3 つのケースは上記と対称です。平均は です。

题意：RT

思路：先将点按点权降順排序、然后一个一个点遍历

假设当前点是i、则只要考虑iと前にすでに通過している点、点 j と点 v が同じ通過成分でない場合 (使用可能)私は、完了した後に追加します、すぐに追加できます、并查集には必要なセットの大きさ