ARC 093 E - Bichrome Spanning Tree

• 問題
• AC

$X$がMSTの重みの総和より小さい場合は実現不可能である。

$X$がMSTの重みの総和に等しい場合、MSTを作れるような塗り方を数えればよい……が、そもそも、だいたいの塗り方においてMSTが作れるように見える。というのも、MSTに使える辺が全部白または全部黒になっているような塗り方を除けばMSTができるからだ。つまり、MSTに使われうる辺が$K$本あるとき、$K$本全部を一色で塗る$2\cdot 2^{M-K}$通りの塗り方以外はMSTを作れる。あとは$K$が求まればよい。これは最小全域木$T$を作った後、$M$本の辺$e = (u, v)$について最適性条件を満たせるか判定すれば数えられる。具体的には、$e$の重みが（$T$上の）パス$u - v$上の重みの$\max$以下であれば$e$はMSTに使える^[1]。変更がないので、$\max$クエリはダブリング等で処理できる。（制約を$N=10^5$と勘違いしていた。愚直でよい。）

$X$がMSTの重みの総和より大きい場合、MSTに使われうる辺は全部白または全部黒に塗られていなければならないので、とりあえず白に塗られているとする。この時、黒に塗られていてMSTに使えない辺が全域木に少なくとも1本含まれていなければならないが、その1本以外は白い辺も自由に選べる。したがって、MSTに対して辺を挿入してそれによってできたサイクルから別の最大辺を削除して全域木を作った時に、重みの総和が$X$になるものを考えればよい。これにはやはり木上の$\max$クエリで答えられる。「MSTの辺と交換した時の重みの総和」が$X$になる辺を$p$本、$X$より大きくなる辺を$q$本としたとき、$p$本から少なくとも一つを黒い辺にする必要があって、$q$本は好きにぬってよいので、塗り方は$(2^p-1)2^q$通り。白の分と黒の分を足すと$2\cdot(2^p-1)2^q$通りとなる。${O}((M+N)\log N)$。

---

厳密な証明がよくわからなかった。

---

1. path optimality condition ↩︎