Codeforces Round #359 (Div. 1) B. Kay and Snowflake
http://codeforces.com/contest/685/problem/B
問題
木が与えられる。頂点 v[i] を根とする部分木の重心を求めるクエリを Q 個処理せよ。
- 2≦n≦300,000
- 1≦q≦300,000
解法
木の根を始点として、最もサイズの大きい部分木を持つ子に移動するという操作を、サイズ n/2 以上の部分木を持つ子が存在しなくなるまで行うことで重心を計算できる。
各頂点に対し次に移動する頂点を求めておき、それを順にたどっていけばいい。辿る操作を高速化するには 1,2,4,8,16,... 手先を計算しておき二分探索するか HL 分解をする。
codechef でこれの木の中心版が出題されていて、そっちは木 DP で解いたんだけど、こっちは HL 分解貼り付けた方が楽な気がして HL 分解で解いた。
結果としてバグを埋め込んで時間を溶かしてしまった…。
