AOJ 2667 Tree (クエリ平方分割解法）

クエリをB個ごとのブロックに分割する。ブロックのはじめにやる処理をSetUp，ブロックのおわりにやる処理をTearDownと呼ぶことにする。

ブロック内のクエリで関係する頂点だけを使って，縮約されたO(B)頂点の森を作る。ブロック内のクエリで関係する頂点とは，具体的には以下のとおり。

この処理はO(N)でできる。

addLazyという配列を作っておき，addLazy[v] += xとする。

根から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)でできる。

もともとの木の根から葉の方向にaddLazyの値を伝搬させて，addCurrentという配列に「もともとの木での根から頂点xまでの距離」が格納された状態にする。

その後でaddLazyを0で埋める。

この処理はO(N)でできる。

$B=O(\sqrt{Q})$ 程度に設定すると，全体として $O((Q+N)\sqrt{Q})$

定数倍高速化をして， $B=3\sqrt{Q}$ 程度にすると2.93secで通った。（何も工夫しないと8secくらいかかって通らなかった）

クエリ平方分割について載っています