解説 | Golden Steiner Tree (Hard)

解説

$A_i = \left\lfloor i\varphi \right\rfloor, B_i = \left\lfloor i\varphi^2 \right\rfloor$ とする。

正整数 $M$ に対して $A_i \le M$ を満たす $i$ の個数を考える。

$i \lt \dfrac{M+1}{\varphi}$

なので、これを満たす $i$ の個数は $\left\lfloor \dfrac{M+1}{\varphi} \right\rfloor$ である。

同様にして、 $B_i \le M$ を満たす $i$ の個数は $\left\lfloor \dfrac{M+1}{\varphi^2} \right\rfloor$ である。

重複を含めると、このグラフの辺の個数 $C_M$ は $C_M = \left\lfloor \dfrac{M+1}{\varphi} \right\rfloor + \left\lfloor \dfrac{M+1}{\varphi^2} \right\rfloor$

$\varphi^2 = \varphi + 1$ より、 $\dfrac{M+1}{\varphi} + \dfrac{M+1}{\varphi^2} = M + 1$ であるため、

$C_M = M$ となる。この等式はすべての正整数 $M$ に対して成り立つため、

$C_{M+1} - C_M = 1$ となるため $A_i = M, B_i = M$ を満たす正整数 $i$ がちょうど $1$ つであると分かる。

よって、数列 $A, B$ には $1, 2, \dots, M$ が $1$ つずつ含まれていることが分かる。

自己ループは無視しても答えは変わらないので $i = A_i = 1$ のときの赤い辺を無視すれば このグラフは木である と分かる。

また、このグラフを頂点 $1$ を親とする根付き木としてみると、木の高さは $\left\lceil\log_{\varphi}{N}\right\rceil = O(\log{N})$ である。

このグラフは頂点 $1$ の自己ループを無視すると木なので、白い頂点をすべて連結にするために残すべき辺は一意に定まり、そのような辺は白い頂点どうしを結ぶパスの和集合である。また、残った辺は部分木をなす。

この部分木に含まれる赤色、青色の辺の個数をそれぞれ $C_R, C_B$ とすると求める答えは $RC_R + BC_B$ である。

頂点 $1$ を根とし、根から頂点 $v$ までのパスに含まれる赤色の辺を 0、青色の辺を 1 として、根から順に並べた 01 文字列を $S_v$ とする。木の高さは $O(\log N)$ なので、 $S_v$ の長さも $O(\log N)$ である。

ここで、 $f(x)=\left\lfloor\dfrac{x}{\varphi}\right\rfloor$ とすると、頂点 $v\ge 2$ の親と、その間の辺の色は以下のように求められる。

したがって、親を繰り返し求めることで、各頂点の $S_v$ を $O(\log N)$ で求められる。

頂点を $S_v$ の辞書順に並べると、赤色の辺を優先して DFS したときの訪問順と一致する。

白い頂点の個数を $k$ とする。白い頂点を $S_v$ の辞書順に並べたものを $v_1,v_2,\dots,v_k$ とし、 $v_{k+1}=v_1$ とする。

頂点 $u,v$ 間のパスに含まれる赤色の辺、青色の辺の個数をそれぞれ $d_R(u,v),d_B(u,v)$ とすると

$C_R=\dfrac12\displaystyle\sum_{i=1}^k d_R(v_i,v_{i+1}),\ C_B=\dfrac12\displaystyle\sum_{i=1}^k d_B(v_i,v_{i+1})$ が成り立つ。

黒色の頂点 $v$ を白色にするときを考える。頂点を $S_v$ の辞書順に並べたとき、 $v$ の直前、直後の白い頂点をそれぞれ $s,t$ とすると

クエリを処理する前では $s\to t$ のパスだったものが、クエリを処理した後では $s\to v\to t$ になる。

したがって、赤色と青色両方について $C\mathrel{+}=\dfrac12(d(s,v)+d(v,t)-d(s,t))$ と更新すればよい。白色の頂点を黒色にするときはこの逆を行えばよい。

また、 $S_u,S_v$ の最長共通接頭辞は頂点 $u,v$ の最小共通祖先までのパスを表すため、 $d_R,d_B$ は文字列の比較によって $O(\log N)$ で求められる。

白い頂点の $S_v$ をset などで管理すれば、頂点の追加・削除は $O(\log Q\log N)$ で行える。辺の重みを変更するクエリでは $C_R,C_B$ は変化しないため、重みだけを更新すればよい。

よって、クエリあたり $O(\log Q\log N)$ 、合わせて $O(Q\log Q\log N)$ でこの問題を解くことができた。