全国統一プログラミング王決定戦本戦 G - Greatest Journey

コンテストではFで辺のコストをmin(C[i],C[j])だと勘違いして破滅しました(こちらも解けるらしいのですが) サンプルに書いてあるやん(絶望)と最後の方に気付いて悲しいね。Gの解説がア(上級者向け)なのでメモを残しておきます。

まず、どういう移動が最適かを考えます。

どの辺も複数回通ってもいいという制約のもと、通った辺のコストが順にa_1,a_2,...,a_Lだとします。

この中のmax=Mをとるindex(複数ある場合は1番左)をpとすると、a_{p+1}...,a_LをMに置き換えてよい(途中から往復し続ける)ことがわかります。

Mに最短で至るまでの経路は全て1回は使わないといけないが、M以前で複数回使うような辺があったとき重複分をMにやってもらった方がいいこともわかるので、iさんはV_iからある頂点まで最短で移動した後、同じ辺(しかもそこまでの経路でmax)を使い続ける形のみを考えればよいです。

次に、こんなの分割統治(重心分解)するしか、ないだろ。という気持ちになるところは多分慣れです。

重心分解では、重心を通る移動のみを考えて後は各部分木に分ければいいので、一旦重心に集めます。V_iから重心Gまでの辺の数をE_i, コストの和をC_iと置きます。

重心GからDFSして各頂点vまでの辺の数をD_v, コストの和をB_v, vの親をp_v, vの親とのコストをw_vとし、V_iからGを経由してvまで行き、vとp_vの間を0回以上往復します。(vまで行って親の方向に往復すると考える方が考えやすいです(子はたくさんあることもあるので))

このとき各クエリiについて、C_i+(L_i-E_i-D_v)*w_v+B_v = C_i+(L_i-E_i)*w_v+(B_v-D_v*w_v) のvについての最大値(vまで辿りつける、つまりL_i - E_i - D_v >= 0の条件の下で)を速く求めたいです。見やすさのためにL_i-E_i をL'_i, B_v-D_v*w_vをB'vとおき、iについての定数項(C_i)を無視すると max L'_i * w_v + B'v (ただし L_i - E_i - D_v >= 0) となり、直線y=w_v*x+B'vたちのうちx=L'_iで1番上にあるものがわかればよいです。

まだ考慮できる頂点にL_i - E_i - D_v >= 0の条件があるため好きな順番に直線を追加する必要があり大変に思えますが、上で見たようにGからvまでのパスにおいてmaxではない辺を複数回使うものは考えなくてよく、maxの辺のみを使うことを再び考えます。(考慮する頂点のうち)適当にvを取ります。x=d(D < D_v)でvが選ばれないことが言えると嬉しいです。素直にvまでの途中の深さdの点をu (D_u = d)とします。uまで潜ったコストはB_u、vでdを代入した値は(D_u - D_v) * w_v + B_vですが、w_vがパス上のmaxという仮定より(B_v-B_u) <= w_v*(D_v - D_u)であるのでvまで潜らない場合の方がコストが良いです。よってL_i - E_i - D_v >= 0の条件を無視して解いても答えは変わりません。(ここがなかなかわからなかった、まあライブラリが強ければ思考停止でいいので)

結局分割統治の各stepではw_vが小さい順に直線を追加していくことで蟻本のenvelopeの管理と同様にdequeででき、O((NlogN + MlogM)logN)でこの問題が解けました。