12/27 PKU

3184 Finicky Grazers

牛を動かして、牛と牛の間の距離を最大化せよ。このとき、牛と牛の間の距離はある整数DまたはD+1になっていないといけない。

DP

1741 Tree

木の上で、距離がK以下になる2点の組み合わせは何通りあるか求めよ。

IOI2011「Race」と解法はほとんど同じ。
分割統治を行う。木の中で適当に１点を設定すると、すべての経路は「その点を通るか通らないか」のどちらかだから、通るものについては各点までの距離を求めて適当に求める。通らないものについては、その後でその点を消去し、再帰的に求める。
分割点の選び方は、木DPを行い、その頂点を除いたときにできる部分木の最大の大きさが最小になるような点を選ぶ。すると、確実にO(N log^2 N)で動作する。
ちなみに、分割点をランダムに選ぶとかなり遅い。「N個の点が直線状に並んだグラフ」に対しては高速であることが期待されるが、「1点から他のN-1個の点へ辺が出ているグラフ」に対してはO(N^2 log N)程度かかってしまう。