TopCoder SRM 695 (Div. 2) Hard. BearUniqueDiameter
問題
木が与えられる。最遠点対が一意に決まるような部分木はいくつあるか。
- 1≦N≦300
解法
木の中心とは、他の頂点との距離の最大値が最小になる頂点のこと。
木の中心には以下の様な性質が成り立つ。
- 中心は 1 個か 2 個。
- 中心は隣接している。
- 直径は中心を通る。
中心が 1 つのとき、最遠点対はかならず中心からの距離 R の点のペアである。ただし中心を通らないペアは除く。
中心が 2 つのとき最遠点対はかならず中心からの距離が R の点のペアである。ただし中心を両方通るペアは以外は除く。
このことを使うと、中心 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 近く掛かってて危なかった。