pekempeyのブログ

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

TopCoder SRM 695 (Div. 2) Hard. BearUniqueDiameter

問題

木が与えられる。最遠点対が一意に決まるような部分木はいくつあるか。

  • 1≦N≦300

解法

木の中心とは、他の頂点との距離の最大値が最小になる頂点のこと。

木の中心には以下の様な性質が成り立つ。

  • 中心は 1 個か 2 個。
  • 中心は隣接している。
  • 直径は中心を通る。

中心が 1 つのとき、最遠点対はかならず中心からの距離 R の点のペアである。ただし中心を通らないペアは除く。

f:id:pekempey:20160721042933p:plain

f:id:pekempey:20160721042937p:plain

中心が 2 つのとき最遠点対はかならず中心からの距離が R の点のペアである。ただし中心を両方通るペアは以外は除く。

f:id:pekempey:20160721043036p:plain

f:id:pekempey:20160721043040p:plain

このことを使うと、中心 N 通り、半径 N 通り、中心の個数 2 通りすべて試して部分木の個数を数えるという方法がうまくいく。

仮に中心を v、半径を R、中心を 1 個としよう。このとき v を根とする木で次のような木 DP を行う。

  • dp[ vertex ][ 深さ R の頂点をいくつ含むか ] := パターン数

ただし深さが R より大きい頂点は無いものとして扱う。根以外で深さ R の頂点を 2 個以上持ってしまうと最遠点対が 2 個以上できてしまうので、根では 2 個以下、それ以外では 1 個以下である。答えは dp[v][2] となる。

次に中心を 2 個としよう。中心を u, v としたとき、辺 (u,v) を削除して u を根とする木と v を根とする木を作り、それぞれに対して次のような木 DP を行う。

  • dp[ vertex ][ 深さ R-1 の頂点をいくつ含むか ] := パターン数

ただし深さが R 以上の頂点は無いものとして扱う。このとき dp[u][1]*dp[v][1] が答えになる。

適当に書いたら 1.6 sec 近く掛かってて危なかった。