AtCoder Regular Contest 162 D問題メモ

AtCoder Regular Contest 162

D - Smallest Vertices

• 「根付き有向木」を以下で定義する
  • 頂点 $1$ を根とし、親から子に向かって有向辺が張られている木
• 「良い頂点」を以下で定義する
  • 頂点 $v$ の部分木に含まれる頂点のうち、最小の頂点番号が $v$ 自身である頂点
• 「良い木」を以下で定義する
  • $N$ 頂点の根付き有向木であり、各頂点の出次数は $d_1,...,d_N$
• 全ての良い木に対する、良い頂点の個数の総和を $\mod{99824433}$ で求めよ
• $1 \le N \le 500$
• $d_1 \ge 1$
• $\sum d_i=N-1$

ケイリーの公式を活用する。

• Cayley の定理と、頂点次数制約のついた全域木の数え上げ - けんちょんの競プロ精進記録

今回の場合、次数 $d_i$ には親に向かう辺がカウントされていないので、$i \neq 1$ の $d_i$ にそれぞれ1を足すと、 無向木の次数に相当するものになる。（が、以下の説明ではとりあえず $d_i$ のままで説明する）

まず、良い木の個数は、ケイリーの公式を使って、以下のようになる。

• $\displaystyle \frac{(N-2)!}{(d_1-1)!\prod_{i=2}^{N}d_i!}$

主客転倒して、各頂点に対して「自身が良い頂点となる良い木の個数」を求め、合計することを考える。

頂点 $1$ と葉は必ず良い頂点なので、良い木の個数だけ存在する。
それ以外の、$i \ge 2, d_i \ge 1$ の頂点について考える。

いま、$v$ の部分木に含まれる頂点集合が $S$ と決まっているとする。
$S$ が $v$ 以上の頂点でのみ構成されていれば、$v$ は良い頂点となれる。

木の頂点数と辺数の関係上、$\displaystyle \sum_{i \in S}d_i = |S|-1$ である必要がある。

$S$ を固定した良い木の個数は、($S$ からできる木の個数) × ($v$ と、$S$ に含まれない頂点からできる木の個数) で 分割して求めることができる。
後者において、$v$ は葉の扱いとなる。

     ○                       ○
   ／  ＼                   ／  ＼
  ○    ○  =         ×   ○    ○
 /  \   ｜                /  \   ｜
○  ⓥ  ○     ⓥ        ○  ⓥ  ○
    /\         /\
   ○○       ○○

※図化のため具体的な木の形状を表現したが、
  実際は、それぞれの木での次数条件を満たす全ての個数を考える

両者をケイリーの公式で表すと、

• $\displaystyle \frac{(|S|-2)!}{(d_v-1)!\prod_{i \in S, i \neq v}d_i!} \times \frac{(N-|S|+1-2)!}{(d_1-1)!\prod_{i \notin S,i \neq 1}d_i!}$

これを整理すると、分母が綺麗な形になる。

• $\displaystyle \frac{(|S|-2)!(N-|S|-1)!d_1d_v}{\prod_i d_i}$

つまり、$S$ の具体的な構成要素に依らず、 $v$ が良い頂点になれる良い木の個数は $S$ のサイズが分かれば計算できることになる。

ただし、辺数の制約（$\displaystyle \sum_{i \in S}d_i = |S|-1$）は満たす必要があるため、 この2つを状態に持ったDPでパターン数を数える。

• $DP[i,j,k]=$ 大きい方から $i$ 個の頂点を見て、$S$ に $j$ 個採用し、その次数 $d$ の和が $k$ であるパターン数

遷移の過程で、以下のような $S$ について、先ほどの式で1パターン当たりの木の個数を求め、答えに加算していけばよい。

• 頂点 $i$ を使っている
• $j=|S|$ としたとき、$k=j-1$ である

$O(N^3)$ で求められる。

Python3