以下の解説では単純パスのことを単にパスと表記し、端点が相異なるパスのみを考えます。

\(X\) を固定した際条件を満たす頂点への色の塗り方が存在するか判定します。

まず辺のうち重みが \(X\) 以上の辺について考えます。この辺を用いるパスの重みは明らかに \(X\) 以上なので条件に対する反例になりえません。よって、条件判定の際はこれらの辺は無いものと考えていいです。

次に重みが \(X\) 未満の辺について考えます。この辺が結ぶ \(2\) 頂点が同じ色で塗られている場合、明らかに条件を満たしません。よって辺が結ぶ \(2\) 頂点は異なる色で塗られてなければならず、重みが \(X\) 未満の辺からなるグラフは二部グラフでなければなりません。

最後に重みが \(X\) 未満の辺からなるグラフが二部グラフであるときの条件判定について考えます。条件を満たすかは連結成分ごとに考えればよく、連結成分内の頂点の色の塗分け方は本質的には \(1\) 通りに定まります。塗分け方が決まったので、あとは同じ色の頂点を結ぶパスの重みの最小値を求めればいいです。このとき、同じ色の頂点を結ぶパスは \(2\) 本以上の辺からなり、特に最初の \(2\) 本からなるパスは同じ色の頂点を結んでおり重みは元の重み以下です。よって条件判定の際は \(2\) 本の辺からなるパスのみを考えればよく、そのようなパスの重みの最小値は簡単に求まります。

以上より \(X\) が固定された場合条件を満たすかの判定は (あらかじめ各頂点 \(v\) を端点とする辺の重みをソートしておくと) \(O(N+M)\) で行うことができます。条件を満たすかについては \(X\) について単調性があるので二分探索することで \(\displaystyle O((N+M)\log {\max_{1\leq i \leq M}{w_i}})\) で求めることができ、十分高速です。

cf.二分探索を用いない解法

上記の議論をもとに考察すると結局答えは元のグラフにおいて

• 辺を \(2\) 本用いるパスの重みの最小値
• \(N\) 頂点 \(0\) 辺からはじめて重みが小さい順に \(M\) 辺を追加していく際、グラフが初めて二部グラフでなくなる辺の重み

のうち大きくないほうだとわかります。

前者については簡単に求まります。後者についても \(2N\) 頂点からなるグラフにおいて、辺の重みが小さい順に

• 頂点 \(2A_i, 2B_i+1\) 間に辺を追加
• 頂点 \(2B_i, 2A_i+1\) 間に辺を追加

した後頂点 \(2A_i,2A_i+1\) が連結であるかどうかを判定することで二部グラフを保っているかどうかが判定できます。これは dsu を用いることで \(O((M+N)\alpha(N))\) で判定することができます。

全体では辺のソートがボトルネックになるので、計算量の評価は \(O(N\alpha(N)+M\log M)\) となります。