Query on a tree (SPOJ 375)

SPOJ Online Judge

http://www.spoj.pl/problems/QTREE/

問題

頂点数Nのツリーが与えら、次のようなクエリがq個与えられるので処理しろ。

  • i番目の辺の重みをtiに変更する。
  • 頂点iと頂点jを結ぶパスの中で最大の重みを答える。

N<=10000
qはたぶん数万

解法

ツリーを鎖に分解して考える。分解の仕方は頂点0から一番遠い頂点までを一つ目の鎖とする。残った頂点集合で再帰的に同じ事をすれば鎖が複数個と鎖同士を結ぶ辺が存在するグラフに変形される。鎖の中にある辺はSegmentTreeで管理すればO(logN)で変更・区間のmaxが取れる。
QUERYの処理で同じ鎖に頂点がない場合は鎖の深さが深い方(同じ深さの場合はどちらでも可)の頂点をSegmentTreeを使って区間のmaxを取りながら一段上の鎖に移動させる。この処理はO(logN)で処理可能。同じ鎖まで到達したら最後に一回SegmentTreeを使って終了。
鎖は最大logNまでの深さにしかならないので全体でO(N+q\log^2N)で処理可能。

追記
鎖に分解する時に一番遠い頂点ではなく部分木のサイズが大きい物を選ばないとO(\sqrt{n})の深さになってしまう。