競プロ典型90問 035

Preserve Connectivity（★7）

Published in

algorithm jp

Apr 6, 2024

木が与えられる。

その中からいくつかの頂点が選ばれる。選ばれた頂点をすべて結ぶ木（元の木を辺を使う）を見つける。このとき辺の数が最小になるように見つける。

想定解法に目を通した者

深さ優先で行きがけに番号を振ると、根に近い方が先になる。

1までの計算が終わっているとする。2の高さを加えてから、1と2の共通の先祖（の一番近いもの）（つまり1）の高さを引くと、1から2までの辺が加えられることになる。

1までの計算が終わっているとする。2の高さを加えてから、1と2の共通の先祖の高さを引くと共通の先祖から2までの辺が加えられることになる。

ソースをよく観察すると端同士で計算を行なっているところがある。その理由は

とすると値は左の図の辺の長さの合計になる。これは「もともとの木の根」から「選ばれた辺で作られる木の根」までの高さが余計に加えられている。

そこで右のように端同士の共通の先祖の高さ求める。この共通の先祖は選ばれた辺で作られる木の根であり、この高さ引くと余計な分がなくなる。

Yの字をイメージすると、右上の頂点と左上の頂点の共通の先祖は3本の線が触れ合っている点である。ここを見つける。

ざっくり言うと二分探索をしているが、すこしトリッキーなので図解する。

現在の候補の範囲の真ん中を調べて2点の先祖が同じなら、下半分を残し、またその半分のところを調べる。

現在の候補の範囲の真ん中を調べて2点の先祖が違っているなら、その違っている頂点に移動して上半分を残し、またその半分のところを調べる。

どっちのパターンでも、32個先を調べたら次は16個先だし、4個先を調べたら次は2個先になるので、調べる距離は毎回半分になっていく。