Loading...
Top Tree
はじめに:writer解は論文を見てしっかり実装したとのことなので、writer解と論文を見るのが一番安全です
結局のところ距離が最小になるような頂点は、X=1の頂点のみに注目した時の重心の頂点です。これは元問題の考察でも使いますね。
なので、この問題は、重心を求めるというクエリと、頂点が与えられたときにそこからのX=1の頂点へのdistの和という2種類のクエリに分解することができます。これを各個撃破します。
Link Cut Tree(LC-Tree)とは、heavy light decompositionを動的に管理するデータ構造です。
LC-Tree / heavy light decompositionでは、木の辺を2種類(heavy edge / light edge)に分類し、効率よくパスクエリを処理します。
LC-Treeでのlight edgeの表現方法は、子から親へ一方的にリンクが張られていたらlight edgeという実装が多いと思います(iwiwiさんの
プログラミングコンテストでのデータ構造 2 ～動的木編～
での実装方法です)。
ここで、子から親への一方的なリンクではなく、親からも今つながっている子の情報を管理しようというテクニックがあります。このテクニックで、パスクエリだけではなく部分木系のクエリも処理できるようになります。
今回の問題ならば、頂点ごとに
子のX=1の頂点の、(その子)の根までの距離の総和(距離の総和を求めるために必要)
子のX=1の頂点の個数の総和(↑を計算するために必要)
X=1の頂点が最も多い子と、その個数(重心を求めるために必要)
を持たせれば十分です。なお、子とは、light edgeでつながっている子(heavy edgeでつながっている子は無視)であることに注意してください。
1,2個目は逆元が存在するのでそのまま総和を持てばよくて、3個目に関してはmultisetとかを使えばよいです(pkmpyさんのコードを見たらpriority_queue2個で実装していました、定数が軽くてよいですね)。edgeのheavy / lightが変化するたびに1,2個目は足したり引いたりして、3個目はinsertしたりeraseしたりします。
計算量ですが、LC-Treeにおいて、edgeのheavy / lightが変化する回数は高々
O
(
log
N
)
O(\log N)
O
(
lo
g
N
)
であることに注意すると、1, 2個目の管理は
O
(
log
N
)
O(\log N)
O
(
lo
g
N
)
、3個目のみ
O
(
log
2
N
)
/
p
e
r
q
u
e
r
y
O(\log^2 N) / \textrm{per query}
O
(
lo
g
2
N
)
/
per query
であることがわかります。当然ならし計算量です。
これでこの問題は解けるのですが、計算量のlogを増やさないことが可能です。
現在のボトルネックは、頂点ごとにmultiset、つまり赤黒木を持っていることです。これを”葉のみに値を持たせる”splay-treeにすればよく、これがtop-treeと呼ばれています、多分！(misawaさんはそうじゃないかなぁと言っていた(数年前なので、記憶が正しければ)し、testerするにあたって自分で確認した限りもそうだと思っています…が自信はないです)。
top-treeにすると、先述の通りlogが落ちるだけではなく、扱えるクエリの種類が増えます(遅延伝搬segtree的なクエリが処理できるようになります)。
tester解は2種類のsplay-treeを実装したくないので、葉以外にも値を持たせるsplay-treeでごまかしています。これでも計算量が落ちているとほぼ確信していますが証明はないです。また、
技術室奥プログラミングコンテスト J - 仕事をしよう！
での
antaさんの実装
はこれだと思います。
参考になるかも:
Link Cut Treeで部分木の情報を管理する - beet's soil
読者層が限定されすぎていませんか？
beet-aizu.hatenablog.com
Please turn on JavaScript to use Paper in all of its awesomeness. ^_^
はじめに:writer解は論文を見てしっかり実装したとのことなので、writer解と論文を見るのが一番安全です