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))
