No.036 D

まずは連結でないと移動できないので, これは Union-Find で管理する.

そして, 街を偶数族と奇数族に分類する. (偶数, 奇数はただの名札であり意味はない)

森と森とをつなぐとき, つなぐの道の距離が偶数のときは, つなぐ街同士の偶奇が一致しなければ片方の森に所属する街の偶奇を反転させてからつなぐ. 森に所属する街が少ない方の街の偶奇を変えればいい. つなぐ街同士の偶奇が一致しているならばそのままつなぐ.

同様につなぐの道の距離が奇数のときはつなぐ街同士の偶奇が異なるようにつなぐ.

これで街が連結で, なおかつ街同士の偶奇が一致していれば偶数距離で移動できるということになる.

続いて, 森内で道を増設するときのことを考える.

つなぐ道の距離が偶数でつなぐ街同士の偶奇が一致している場合, またはつなぐ道の距離が奇数でつなぐ街同士の偶奇が異なる場合はそのままつなげばいい. (すなわち, 何もしなくてもいい)

そうでない場合は, 奇数の長さのループができることになり, このループを適当に周回することで森内のあらゆる街間が偶数距離で移動できるようになる. 以降にこの森に別の森がつながる場合は, そのつながる森に含まれる街もふくめて自由移動が可能となる.