良いグラフの条件で述べられた性質を持つ全域木を「良い全域木」ということにします。まず固定されたグラフに対する良い全域木の存在判定方法を考えます。

良い全域木が存在する場合、（狭義）単調増加数列 \(X\) を用いて辺 \((u,v)\) のコストを \(|X_u-X_v|\) と定めたとき、 良い全域木は最小全域木の一つになります。これは良い全域木に含まれない辺 \((u,v)\) に対し、 \(u,v\) を結ぶ単純パス上の辺のコストは \(|X_u-X_v|\) 未満であることとクラスカル法からわかります。

とくに \(X_u=10^u, -10^{N-u}\) としたときのことを考えると、各辺のコストは相異なるため最小全域木は一意に定まり、良い全域木は

• 辺 \((u,v)\) のコストが \((N+1)v-u\) であるときの最小全域木 \(T_1\)
• 辺 \((u,v)\) のコストが \((N+1)(N+1-u)-(N+1-v)\) であるときの最小全域木 \(T_2\)

のいずれにも等しくなります。よって、 良い全域木が存在するには \(T_1=T_2\) が成り立つことが必要です。

逆に

• \(T_1\) において、辺 \((u,v)\) に対し \(u,v\) を結ぶ単純パス上の頂点番号の最大値はかならず \(v\) である

• \(T_2\) において、辺 \((u,v)\) に対し \(u,v\) を結ぶ単純パス上の頂点番号の最小値はかならず \(u\) である

が成り立つことからこれは十分条件でもあります。

以上より良い全域木の存在判定は \(T_1,T_2\) を求めて一致判定を行うことでできます。

すると各辺が削除された場合の良い全域木の存在判定は、辺が削除された場合の最小全域木の変化を求めて一致判定を行えばできます。

グラフ \(G\) の最小全域木 \(T\) に対し、 辺 \((u,v)\) を削除して得られるグラフの最小全域木 \(T_{u,v}\) は以下の手順で得られます。

• \((u,v)\) が \(T\) に含まれない場合、 \(T_{u,v}=T\) である。そうでない場合、 \(T\) から \((u,v)\) を除く。その結果 \(T\) は \(2\) つの連結成分に分かれる。 \(2\) つの連結成分をまたぐ辺のうち、コストが最小のものを \(T\) に追加して得られた木が \(T_{u,v}\) である。

よって以下の問題が解ければいいです。

グラフ $G$ の最小全域木 $T$ の各辺 $e$ に対して、変数 $X_e$ を $X_e=\infty$ で初期化する。 グラフ $G$ の辺のうち、 $T$ に含まれない辺 $(u,v)$ に対して、 $T$ 上で $u,v$ を結ぶ単純パスに含まれる各辺 $e$ について $X_e \leftarrow \min(X_e,C_{u,v})$ （ $C_{u,v}$ は辺 $(u,v)$ のコスト）と更新した後の $X_e$ をすべて求めよ。

これは dfs しながらセグメント木で range chmin query を処理することで \(O(M\log N)\) 時間で処理することができます。もしくは木を重軽分解して heavy path を並べることで \(O(\log N)\) 回の range chmin query に変換できるため、 \(O(M\log^2N)\) 時間で処理でき、こちらでも間に合います。