問題概要

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

これも組合せの数を考えるのに苦労しました。さらに2重にDPを使う必要もあって理解困難。

解法

木の問題なので部分問題として子の部分木を使うのは常道かと思います。親から見たときに子それぞれを根とした部分木での$j$本のdisjointなパスを書く組み合わせの数がわかっているとします。すると、親から見たときに$K$本のパスを書く組み合わせは、子1の部分木から1本、子2の部分木から1本、子3の部分木から$K-2$本書く組み合わせとか、子2から3本、子3から$K-3$本などの組み合わせを考える必要があります。

言い換えると、いろいろなものがいくつかの袋の中に入っていて、ある袋から$j$個の物を取り出す組合せの数がわかっているとします。どの袋からいくつとってもいいとして、合わせて$K$個の物を取り出す組合せの数を求めるような問題となります。

この組み合わせの数を求めるにはナップサック問題のようなDPが必要になります。$i$番目までの子を使って、$j$本のパスを書く組み合わせの数$dp2[i][j]$は、子$c_i$の部分木で$j$本のパスを書く組み合わせが$path[c_i][j]$とすると、$dp2[i][j]=\displaystyle\sum_{k=0}^{j}dp2[i-1][j-k]\cdot path[c_i][k]$のようになります。

typicalDPP

ここまでは子の部分木でできるパスの組合せのみでしたが、これに親から子に辺を引くことで増えるパスの組み合わせを考慮しなければいけません。「disjointなパス」ということから、親から3つの子に辺があるようなパスは条件に合いません(親を2回通らないと書けないから)。条件に合うパスは、親から見たときに子に対しての辺は0,1,2本のどれかになります。また、子に辺をつなげる際にすでにその子の部分木で、子から孫に対して2本の辺が書いてるパスが含まれる場合は新たなパスにすることができません。このように、パスの組み合わせの中に親から何本の辺が書かれているのかというのを状態として管理しなければいけません。

ということで、子$c_i$の部分木で、その子から孫に対しては$l$本の辺$(l=0,1,2)$が出ているパスを含み、合わせて$j$本のパスを書く組み合わせの数を$path[l][c_i][j]$とします。 この時、先ほどのDPでは$i-1$番目までの子の部分木で書ける組み合わせと$i$番目の子のこの部分木で書ける組み合わせをかけていましたが、親$v$からどのような辺を引くかによって、選べるパスの組合せに制限が付きます。

  1. 親$v$からの辺が0本になる組み合わせ
  2. typicalDPP0
  3. 親$v$からの辺が1本になる組み合わせ
  4. typicalDPP1-1
    typicalDPP1-2
    typicalDPP1-3
  5. 親$v$からの辺が2本の組み合わせ
  6. typicalDPP2-1
    typicalDPP2-2
    typicalDPP2-3
漸化式の定義: $$\begin{eqnarray} dp2[0][i][j] & += & dp2[0][i-1][j-k]\cdot path[0][c_i][k]\\ dp2[1][i][j] & += & dp2[0][i-1][j-k]\cdot path[1][c_i][k]\\ & + & dp2[1][i-1][j-k]\cdot path[*][c_i][k]\\ dp2[1][i][j+1] & += & dp2[0][i-1][j-k]\cdot path[0][c_i][k]\\ dp2[2][i][j] & += & dp2[1][i-1][j-k]\cdot path[0][c_i][k]\\ & + & dp2[2][i-1][j-k]\cdot path[*][c_i][k]\\ dp2[2][i][j-1] & += & dp2[1][i-1][j-k]\cdot path[1][c_i][k]\\ \end{eqnarray}$$

$dp[l][i][j]$:$i$番目までの子の部分木を使って、$j$本のdisjointなパスを書ける組み合わせの数のうち、親$v$からの辺の数が$l$のパスを含んだものの数。

$path[l][c_i][k]$:親$v$から見て子$c_i$を根とする部分木に含まれる$k$本のdisjointなパスを書ける組み合わせの数のうち、子$c_i$からの辺の数が$l$のパスを含んだものの数。$path[*][c_i][k]=path[0][c_i][k]+path[1][c_i][k]+path[2][c_i][k]$を意味する。

$i$:親$v$から見たときにその子$c_1~c_m$の何番目を処理しているのかを表す$(0\le i\le m)$。

$(0\le j\le K+1,\ 0\le k \le j)$。

初期値:$dp2[0][0][0]=1$

求める解:$path[l][v][j]=dp2[l][m][j]\ (0\le j\le K+1,\ l=0,1,2)$親$v$を根とする部分木に含まれるパスの数がこのDPで求められる。

このように親$v$に関する組み合わせの数を求めるために、その子のDPが済んでいないといけないので、適当な木全体の根を決めてから、子にあたる$c_i$を選択してDPする必要があります。$j$ですが、途中の漸化式で左辺が$j-1$になるところがあるため、$j=K+1$の組合せ数も必要になります。従って、$O(n\cdot K^2)$程度になると思います。$l$のループは展開しているので数えていません。

最終的なこの問題の解としては、木全体の根($root$)について$path[*][root][K]$になります。

さらに$i$のループですが、子のDPを先にやるために木全体の根から再帰のDFSでやってみたところ、多分$n=1000$くらいのケースなのでしょう、1ケースだけJavaではTLEになりました。なので、キューなどを使って先に木全体を走査して、葉の方からやるための順番を作ってからDPを行う必要がありました。

考察

この辺りの問題はコンテストの時間内になんて絶対解ける気がしません。TDPCではお二人の方が解かれていましたけど。。。