導入
次の問題を解きます。
出典： yukicoder No.902 Query ζone
動的木上で、与えられる $k$ 頂点をすべて含む部分木に含まれる辺の重みの総和の最小値を求めるクエリを処理してください。頂点数、 $k$ の総和はそれぞれ $10^5$ 以下です。
発案者の niuez さんは、部分木内の位置関係に着目し、 cluster 毎にユーザー定義のパラメータを $7$ 個もつ top tree を用いて解きました。
今回は辺を採用する条件に着目し、 cluster 毎のパラメータが $\sout{5}$ 個 $4$ 個（2022/12/25更新）となる解法を提案します。
解説
重みの総和を最小化する部分木に含める必要がある辺を必要辺と呼びます。クエリごとに与えられる頂点を赤頂点と呼びます。また、 cluster に対応させる情報は boundary vertex の情報を考慮しないとします。
頂点毎に管理するユーザー定義の情報はその頂点が赤頂点かどうかの情報のみです。その頂点を expose することで更新できます。
cluster の $2$ つの boundary vertex を $l$ , $r$ とします。用いる top tree は、 cluster ごとに次のパラメータを持ちます。
- (0) cluster 外に赤頂点がない場合の必要辺の重みの総和
- (a) 上記以外で、 cluster 外に $1$ つ以上の赤頂点があれば必要辺になる辺の重みの総和
- (b) 上記以外で、 $l$ 側に $1$ つ以上の赤頂点があれば必要辺になる辺の重みの総和
- (ab) 上記以外で、 $r$ 側に $1$ つ以上の赤頂点があれば必要辺になる辺の重みの総和
- (a+b) 上記以外で、 $l$ 側に $1$ つ以上かつ $r$ 側に $1$ つ以上の赤頂点があれば必要辺になる辺の重みの総和
cluster に赤頂点があるかどうかは、このうち (0)(a)(b)(a+b) の $4$ つのいずれかが非零であることと同値であり、パラメータから除外できます。
cluster を合併する際の計算では、 $2$ つの cluster と新たに cluster に含まれる( underlying tree 上の)頂点の情報を用います。
正当性の証明には、各パラメータが合併後にどのように寄与するかを考えると都合がよいです。寄与する先は得られる情報から一意に決まるので、合併後のパラメータを正しく計算できるという形式で証明できます。
次に (a+b) を消去します。 (a+b) の寄与は、 (a)+(b)-(ab) で表現できるので、それに従って計算式を更新すると (a+b) がパラメータから消去されます。 cluster に赤頂点があるかどうかの条件については、 (0)(a)(b) のいずれかが非零であることと同値になります。
解答例
self-adjusting top tree ( http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.87.9754&rep=rep1&type=pdf ) から circular order を無視したものを用いています。 top tree のインスタンスを表すコードは $734$ 行目から $808$ 行目までです。パラメータ名は必要辺となる条件を表します。