問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2667
解法
クエリをB
個ごとのブロックに分割する。ブロックのはじめにやる処理をSetUp,ブロックのおわりにやる処理をTearDownと呼ぶことにする。
SetUp
ブロック内のクエリで関係する頂点だけを使って,縮約されたO(B)頂点の森を作る。ブロック内のクエリで関係する頂点とは,具体的には以下のとおり。
- addクエリで指定された頂点
v
- distanceクエリで指定された2つの頂点
u
,v
とLCA(u,v)
この処理はO(N)でできる。
クエリ処理
addクエリ
addLazy
という配列を作っておき,addLazy[v] += x
とする。
distanceクエリ
根からu
, v
, LCA(u,v)
までの距離が分かればよい(「その他の解法」のリンク参照)ので,根から頂点x
までの距離を計算する方法を考える。これは縮約された森でx
から根まで辿ることで,以下のような方法で計算できる。
ans = 0 y = x while y has parent: y = parent(y) ans += addLazy[y] * (depth(x) - depth(y)) return ans + addCurrent[x]
addCurrent
の意味はTearDownで説明する。parent
は縮約された森での親,depth
はもともとの木での頂点の深さである。
縮約された森では頂点数はO(B)個なので,この処理はO(B)でできる。
TearDown
もともとの木の根から葉の方向にaddLazy
の値を伝搬させて,addCurrent
という配列に「もともとの木での根から頂点xまでの距離」が格納された状態にする。
その後でaddLazy
を0で埋める。
この処理はO(N)でできる。
計算量
- SetUpはO(N)の計算量で,O(Q/B)回呼び出される
- addクエリはO(1)の計算量で,O(Q)回呼び出される
- distanceクエリはO(B)の計算量で,O(Q)回呼び出される
- TearDownはO(N)の計算量で,O(Q/B)回呼び出される
程度に設定すると,全体として
コード
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1571415
定数倍高速化をして,程度にすると2.93secで通った。(何も工夫しないと8secくらいかかって通らなかった)
参考
クエリ平方分割について載っています
その他の解法
- Euler-Tour + セグメント木 http://rippro.org/event/ritscamp2015/F.pdf
- HL分解 http://tubo28.me/blog/post/2015/10/28/aoj2667/