pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

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 分解をする。

gist.github.com

codechef でこれの木の中心版が出題されていて、そっちは木 DP で解いたんだけど、こっちは HL 分解貼り付けた方が楽な気がして HL 分解で解いた。 結果としてバグを埋め込んで時間を溶かしてしまった…。