Sorted Paths

最短パス $(u,v)$ を $f(u,v)$ の昇順に数えていけばよいです。一例として以下のような方法が考えられます。

• $N$ 頂点 $0$ 辺のグラフ $G$ と変数 $cnt=0$ を用意する。
• 各 $x\in \{C_i\}$ について昇順に以下の操作を行う。
  1. $\max(C_{A_j},C_{B_j})=x$ かつ頂点 $A_j$ と頂点 $B_j$ が連結でないような $j$ が存在しなければ終了する。存在すればそれらのうち一つを選び、$($頂点 $A_j$ を含む連結成分のサイズ$)\times($頂点 $B_j$ を含む連結成分のサイズ$)$ を $cnt$ に加算した後、無向辺 $(A_j,B_j)$ を追加する。
  2. このとき $K \le cnt$ であれば答えは $x$ である。
  3. 1.に戻る