N – 木 解説(AtCoder Typical DP Contest)

2020年3月31日AtCoder剰余, 動的計画法, 数え上げ, 逆元, 木DP, 部分木, 階乗

問題へのリンク

問題概要

木が与えられる。辺が常に連結になるように木を描く。何通りの描き方があるか、mod 1,000,000,007 で求めよ。

制約

  • \(2 \leq N \leq 1000 \)

考え方

前提:木DPの考え方

俗に言う、木DP を用います。木DPでは以下のようなDPを基本に考えます。

dp[ v ] := 頂点 v を根とする部分木についての何かしらの値

それぞれの部分木から、ボトムアップ的に dp を計算していきます。以下のように、子を根とする部分木を組み合わせて新しい木をつくるイメージです。

頂点2・3・4を根とする部分木3つ
頂点1を根とする(部分)木

木DPの適用

以下のようなDPを考えます。

dp\({}_r\) [ v ] := 頂点 v を根とする部分木の辺の描き方。ただし、辺は v に接続するものから描くとする。また、元々の木は r を根とする。

これの計算方法は少し分かりにくいので、具体例を見てみます。

右の図で dp\({}_1\)[ 1 ] を求めることを考えてみましょう。

頂点2,3,4を根とする部分木の値は以下のように既に計算できているものとします。

  • dp\({}_1\)[ 2 ] = 1 通り
  • dp\({}_1\)[ 3 ] = 2通り
  • dp\({}_1\)[ 4 ] = 1通り

それぞれのcを根とする部分木の辺数に1(cからvへの辺)を加えた値は以下のようになります。

  • sub\({}_1\)[ 2 ] = 1 辺
  • sub\({}_1\)[ 3 ] = 3 辺
  • sub\({}_1\)[ 4 ] = 2 辺

この時描きたい辺は6辺あり、

  • 1番目から6番目を、3つの部分木に振り分ける方法:\(\frac{6!}{1!3!2!}\) 通り
  • それぞれの部分木で何通り描き方があるか:\(1×2×1\) 通り

のようになります。よって全体では

$$1×2×1 × \frac{6!}{1!3!2!}$$

です。

辺を描く順番の一例

それぞれの頂点を根として木DPを行う

先程は、「根とした頂点から辺を描き始める」ということを決めて木DPを行ったので、全ての描き方を数えるためには、それぞれの頂点について、木DPを繰り返さなくてはなりません。

その際に、同じものを重複して1回ずつ数えることになるので、最後に全体を2で割る必要があります。

解法

それぞれの頂点について、根 r とした時の木DPを以下のように行い、dp\({}_r\) [ r ] の総和を2で割ったものが答えになります。

dp\({}_r\) [ v ] := 頂点 v を根とする部分木の辺の描き方。ただし、辺は v に接続するものから描くとする。また、元々の木は r を根とする。

このようにすると、頂点 v の子 c を根とする部分木を組み合わせて以下のように計算することができます。cを根とする部分木の辺数に1(cからvへの辺)を加えたものを sub\({}_r\)[ c ] などとすると

  • dp\({}_r\)[ v ] =( \(\prod_{c}\) dp\({}_r\)[ c ] ) × \(( \sum_{c}\) sub\({}_r\)[ c ]\()!\) / \( (\prod_{c}(\) sub\({}_r\)[ c ] \(!))\)

※ 実際に dp をforループなどで更新するのは大変なので、dfs などを利用して計算すると楽になります。

※ 階乗や階乗の逆元の計算は、前処理を行っておくことで \(O(1)\) で計算することができます。

C++ での実装例

長いですが、前半部分はただのライブラリです。

剰余の計算が楽になるように ModInt 構造体を、階乗や階乗の逆元の計算が楽になるように、Comb構造体を利用しています。

参考:全方位木DP

頂点数が多い場合でも、全方位木DPと呼ばれる動的計画法を用いることで、\(O(N)\) で求めることができます。

先程は各頂点ごとに木DPを行いましたが、同じ部分木が何度も登場するのでその分を上手く再利用してやることができます。