問題概要

問題文はこちらを参照してください。

DPの問題というよりも、組み合わせの数を数える部分の理解に苦労しました。期待値の時もそうなんですが、確率の勉強大事。

解法

まずは下記のような具体的な例を考えます。頂点$i,j$の辺があるとして、頂点$j$の右側に連結を保ちながら辺を描く順番を考えます。

typicalDPN

実際には、辺を描く順番としてACDEB, ACDBE, ACBDE, ABCDE, BACDE, ADCEB, ADCBE, ADBCE, ABDCE, BADCE, ACEDB, ACEBD, ACBED, ABCED, BACEDの15通りになります。連結を保つという制限がなければ、辺を描く順番の組み合わせの数は辺の数分の並べ替えで$5!$通りですが、Aよりも先にその右側にある辺(C,D,E)を描けない、Cよりも先にその右側にあるEを描けないという組み合わせ分を除かなければいけません。

ここで、辺Aが既にあるとして、頂点$1$の右側に連結を保ちながら辺を描く順番の組み合わせがわかっている(実際は3通り)とします。すると先ほど考えた5つの辺の並べ替えのうち、ACDEの部分は先頭がAで、残りは3通りしか許されないということになります。つまり、$5!$をACDEの並べ替えの数$4!$で割って、実際に許される組合せの数$3$をかけることで求められます。

$dp[i][j]$を辺$i,j$があるとして、頂点$j$の右側に連結を保ちながら辺を描く組合せの数とし、$vn[i][j]$を頂点$i$を親側と見て、頂点$j$の配下にある辺の数とします。すると次の式が成り立ちます。

$$dp[i][j]=vn[j][j]!\cdot\frac{dp[j][1]}{(vn[j][1]+1)!}\cdot\frac{dp[j][2]}{(vn[j][2]+1)!}$$

(頂点1側の辺を描く組み合わせは$(vn[j][1]+1)!$通りあるが、条件を満たすのはそのうち$dp[j][1]$通りだけ。頂点2側も同様)

このように、$dp[i][j]$は頂点$j$の配下の辺に関する部分問題$dp[j][1],dp[j][2]$を使って解くことができます。

漸化式の定義: $$dp[i][j]=vn[i][j]!\cdot\prod_{k}\frac{dp[j][k]}{(vn[j][k]+1)!}$$ $$vn[i][j]=\sum_{k}vn[j][k]+1$$

$dp[i][j]$:辺$i,j$があるとして、頂点$j$の右側に連結を保ちながら辺を描く組合せの数。

$vn[i][j]$:頂点$i$を親側と見たとして頂点$j$の配下にある辺の数。

$k$:頂点$j$からつながる頂点のうち、頂点$i$ではないもの(頂点$i$を親側と見たとして、頂点$j$の子となる頂点)。$E$を木の辺の集合としたとき、辺$(j,k)\in E$かつ$k\ne i$を満たす。

$i,j$:辺$(i,j)\in E\ $($i$と$j$を入れ替えたものも含めて$2(n-1$個)

初期値:条件を満たす$k$が存在しないとき(頂点$j$が葉であるとき)、$dp[i][j]=1$,$vn[i][j]=0$

この漸化式からボトムアップのループを決めるのは自分には無理なので、実装はメモ化再帰を用いました。

また、階乗の計算が出てきますが、それはすべて辺の数になっているので$n-1$を超えることがありません。これについては事前に$fact[n]$などとして、$n!$を$MOD$で割った余りを$O(n)$で計算することができます。また、階乗の割り算も出てきますが、こちらについては素数での剰余なので、$ifact[n]$などとして、$n!$の逆元を同様に求めておきます。

これで定義した$dp[i][j]$については求まりますが、最終的な解は次のようになります。先ほどと同じように辺$i,j$の右に$vn[i][j]$個の辺があって、条件を満たす組合せは$dp[i][j]$個、また、左には$vn[j][i]$個の辺があって、条件を満たす組合せは$dp[j][i]$個。したがって、辺$i,j$を最初に描いた時の組み合わせの数は$(vn[i][j]+vn[j][i])!\cdot\frac{dp[i][j]}{vn[i][j]!}\cdot\frac{dp[j][i]}{vn[j][i]!}$となります。これをすべての辺について足したものが解になります。

$\displaystyle\sum_{辺(i,j)\in E}(vn[i][j]+vn[j][i])!\cdot\frac{dp[i][j]}{vn[i][j]!}\cdot\frac{dp[j][i]}{vn[j][i]!}$($n-1$個の辺についての和)

考察

$dp[i][j]$は辺の数の2倍分の組み合わせしか有効ではないですし、$k$のループも全体で辺の数の2倍しかないので、$O(n^2)$にもならないのではないかと思うのですが、ちゃんと計算できないのでわかったら追記しようと思います。

逆元についての詳細は省きますが、組み合わせの数の問題ではぜひ知っておきたい知識だと思います。逆元使わないとこの問題も解けないのではないでしょうか。(Combinationで表してパスカルの三角形でも解けるようです)