Regions(地域) - joi2010-day2 解説

筆者: qnighy

木を、最大の直径が最小になるようにM個の部分木に分割する問題である。

直径の計算

本題に入る前に、木の直径の計算方法を確認しよう。

(二度の深さ優先探索で求める方法もあるが、これは今回の問題では使わないので省く。)

木の直径は木構造に対する動的計画法で求めることができる。

木に根を設定したとき、その直径は必ず、いずれかの頂点から2方向に下向きに伸びる経路で表現される。

そのため、各頂点について、そこから伸びる経路で、最長なものから2つ分を動的計画法で計算すれば良いことになる。

M=2, O(N^2)解法

M=2ということは、ちょうど1つの辺を切断するということである。

ということは、全ての辺について、その辺の両側にできる部分木の直径をO(N)で求めれば、O(N^2)で計算できる。

この方法ならば20点を獲得できる。

M=2, O(N)解法

O(N^2)では20点しか獲得できないので、O(N)を考える。

(省略)

これで40点を獲得できる。

O(NlogN)解法

Mが一般の場合を考えよう。

この問題は、その性質から、二分探索が適用できることがすぐわかる。

すると、「最大直径dの制限下で効率よく分割したとき、地域がM個以下になるか」という問題をO(logN)回解けばよいことがわかる。

この解法の肝は、直径を求めるときと同様の木DPの過程で、部分木を切り離す操作を行なってしまうことにある。

明らかに、木DPの過程で、木を切断する位置は上のほうがよい。そのため、必要に応じて切り離していけば、自動的に最適の分割となる。

いつ切断が必要になるかを考えるために、「処理途中の頂点の集合」について考える。

最初、「処理途中の頂点の集合」は空であり、DPの配列には、その頂点から「処理途中の頂点」を辿って行ける最も深い経路の長さを記録しておく。

頂点を深いものから処理していくとき、その頂点を「処理途中の頂点の集合」に追加しようと試みる。しかし、それを追加したときに、その親を頂点とする部分木の暫定直径がdをオーバーする場合は、その頂点または保存された経路のどちらか(長いほう)を削除しなければならない。このとき切り離しが起こる。これを繰り返すことで、必要な切り離しの回数がわかる。

この処理はO(N)で行えるので、全体ではO(NlogN)となり、これで満点を獲得できる。