機械的に列を木に拡張するテク
はじめに
多分どっかで既出です。
お気持ちの説明
列上で行える累積和的な操作( f(x~y)=f(x~z)+f(z~y) みたいになっているもの)で構成される操作を、木上のパスで行うテクです。こういう操作でなくても物によっては出来ることもあります。
「根が関係ないような問題でも、根を適当に決めるとそこからの相対値でクエリを求める事が出来る」という風に思っておくと分かりやすいかもしれません。
具体的に説明するのは難しいので、例をいくつか出します。
X-Yパスの長さを求める
列上問題であれば、累積和配列を持って B[Y]-B[X] (X < Y) という風にすると求める事ができます。
木上クエリに拡張した場合、頂点0を根とすると
0-Xパスの長さ + 0-Yパスの長さ - 2*(0-LCA(X,Y)パスの長さ)
とできます。（これはただのダブリングでもできるので嬉しさはありません）
（このようにして木上のパスの長さを求める問題に、JOIの道路整備などがあります。）
モンスターショー
列上のクエリの場合だと、集める頂点をTとしたとき、
(スライム全ての座標の値の総和) - ( T*(Tよりも前の列にいるスライムの数) - Tよりも前のスライム全ての座標の値の総和) ) - ( T*(Tよりも後ろの列にいるスライムの数) )
とすることによって求める事ができます。
これを木上に拡張した場合はこの問題の解説を読んでください。
まとめ
「列上で、累積和みたいな操作と一点更新・一点取得で出来る操作をする問題」があったときに、この列を木上の1-tパスとみなすことによって機械的に木に拡張することができます。
累積和のところはHLDなどを使うことで行えることが多いと思います。
適当な列上の操作を思いつけるだけで難しい問題になるので、作問時に役立ちます。
また、木上の変なことをする問題を見た時に、「とりあえず根を固定してそこからの相対パスで考えよう」という発想を持っておくと、問題が解きやすくなります。
最後に、こういう風に機械的に作られた問題は面白くないものが多いので、真面目に作問をしたほうが良いと思います。
また、LinkCutTreeなどで殴られて悲しい思いをする事もあります。
ただ、300点問題に出来そうな列上のクエリ問が生えたときにこの記事の存在を思い出してもらえると、作問ストックに高難度が仲間入りするかもしれません。
