[問題案] Minimum Distance Sum On Tree (Incremental)

[maspypy]

問題概要

木がある。辺重みがある。

順列 $p_0, \ldots, p_{n-1}$ が与えられる。 $k=1,2,\ldots,n$ に対して次に答えよ：
$S = {p_0,\ldots,p_{k-1}}$ とする。 $f(v) = \sum_{s\in S} dist(v, s)$ とするとき、 $\min_v f(v)$ を出力。

制約

$5\times 10^5$ とか？

解法

重心を管理する。1 頂点追加すると、重心はそのままの位置のままにできるか、
そうでない場合は、追加頂点の方向に進む。（木を圧縮したときの次の頂点みたいなところに行く。）

LCA, EulerTour+FenwickTree くらいで全部できるはず。$O(N\log N)$。

---

直近で複数回欲しくなったので。

分かっていないこと。

• 最小値を与える点を $S$ の重心などと呼ぶのは適切か？
  • ある程度まともな用語なら、問題概要を「重心を出力せよ」にしてもよさそう。
• $S$ に対する削除操作がある場合の簡潔な実装。
  • HLD+遅延セグ木パスクエリとかがあれば出来ると思ったんですが、実行時間も実装量もまあまあ変わりそうな気がした。同程度でできるならば 1 問にまとめてもよいと思ったんですが。

その他。

• 最小値を与える $v$ を出力してもよい（ジャッジを作るのがすこし大変になる）。

---

参考：動的木の場合
https://yukicoder.me/problems/no/772

[hos-lyric]

参考：動的木の場合の元ネタ
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2636

[noshi91]

自由に根付き木にして、重心を毎回 1 から計算することにします。重心の内最も根に近いものを c とすると、c を根とする部分木の重みは全体の重みの半分を超えます (全体の重みが 0 の場合を除く)。部分木の重みは DFS pre-order で並べた列の区間和として表現されるわけですが、この列で左端から見て重みが半分になる位置 h を考えると、c についての区間は必ず h を含みます。よって、c の候補が根からのあるパス上に絞られました。
残りの部分ですが、HL 分解したときの light edge についてその辺の下の部分木の重みを管理しておくことが O(log(n)) でできるので、この情報を使って c がどの chain にいるかを O(log(n)) で判定して、chain の上のどこにあるかを二分探索します。DFS を HLD の heavy edge が最後に来るような順序で行うと、chain 上の頂点に対応する区間は右端が一致するので、セグ木内二分探索になります。

ここまでやるなら top tree を持ち出した方が良いのかもしれない。

[hotman78]

根から過半数を子孫に持つ頂点を辿っていく事で重心に突き当たる事から、答えはS上の過半数の頂点の祖先になるので、見つかるまでS上の頂点を選んでダブリングを繰り返すアルゴリズムが作れそうです
乱択アルゴリズムなのが難点ですが、これはとてもシンプルだと思います

[hotman78]

根から過半数を子孫に持つ頂点を辿っていく事で重心に突き当たる事から、答えはS上の過半数の頂点の祖先になるので、見つかるまでS上の頂点を選んでダブリングを繰り返すアルゴリズムが作れそうです 乱択アルゴリズムなのが難点ですが、これはとてもシンプルだと思います

https://twitter.com/hotmanww/status/1658641996981088256
これのリプツリーにてnoshiさんにご指摘いただいた通りあまり筋が良くはありませんでした

[maspypy]

いまのところ、割と実装量が変わりそうなので、この issue に関しては Incremental ということにします。
（AOJ にある情報により個人的には満足してしまったのですが）

[maspypy]

作業者募集。

[NachiaVivias]

この問題では木の根は関係ないので各辺の両端の点を与えるのがよいと思いますが、そうすると「動的木の場合の元ネタ」がそうであるように、順列 p を与える必要が皆無だと思います。 p 無くしませんか？

[maspypy]

なくせるのはそうなんですが、なくした方が問題設定が自然であるとはあまり思っていないです。

[NachiaVivias]

むしろ問題の綺麗さだったら余計な順列を挟まないほうが察しやすくてよいと思いますが。

オンラインクエリを意識して作ったからそっちのほうが自然だ、という意味だったら、それもありだと思います

[maspypy]

個人的に頂点ラベルはラベル以上の意味を持たせることに消極的です。
（例えば Shortest Path は 0 -> N-1 よりも s -> t とする方が好みです。）
好みレベルだとは思うので、作業者がなくしたいといえばなくしていいという気持ちではいます。