読者です 読者をやめる 読者になる 読者になる

らての精進日記

修行をします

aoj1330:Never Wait for Weights

解法

各重りを頂点とみなしてみる。
! a b wタイプのクエリが来たら、aとbに辺を張る。? a bタイプのクエリが来たとき、aとbが同じ連結成分に属していれば、答えが求められる。

連結性の判定にはUFが使える。UFをうまいこと書き換えて値の計算も行えるようにしたい。

各頂点について、根からの差分dを持つ。(すなわち、頂点vが含まれる木の根をrとしたとき、d[v]=w[v]-w[r])

!a b wタイプのクエリが来たとき、どうどのように更新すればよいか考える。

aが含まれる木を、bが含まれる木の下にくっつける。a側の木では、dの値はa側の木の根に基づいている。よって、a側の木の頂点について、dが変化する。具体的には、d[b]-d[a]-wだけ増加する。

これを愚直に足していくと最悪O(NQ)になって死ぬ。そこで、マージテクを用いて木のサイズをいい感じにしていくことで、O(NlogN)とかになる。

はむこさんの回答をみたんですが、「根からの差分を持つ」ではなく「親からの差分を持つ」という風にやっていて、こうすると実装が楽になるからよさそうだった

親からの差分を持つ:
・辺の縮約ができないので、マージテクでオーダーを落とす
・書き換えるのはaの根だけでいい

根からの差分を持つ:
・辺の縮約はできる
・書き換える場所がいっぱいあるので、マージテクで書き換える場所を減らす。ただし、どこを書き換えればいいのかわからなくなるので、木に含まれる頂点がすべて入ったsetをマージしていく。(今気づいたけど、setじゃなくてvectorでいい)

辺の縮約ができるかどうかの差のように見えるが、結局どっちもマージテクでオーダーが落ちるので、オーダー的には大して差がでない(前者はlogNで後者はアッカーマン関数逆関数(N))