ABC160 F - Distributing Integers - ツバサの備忘録

解法

$k = 1$ のみの場合について答えることができればあとはうまく伝播させて全方位木DPにしてしまえばよいので、 $k = 1$ の場合を考えます。

$dp[i] = i$ を根とする部分木についての、数字の配置パターン数
$c_i = i$ を根とする部分木の頂点数

とします。 $c$ の計算方法については、よくある問題なので省略します。
数字の配置パターン数、というのは、その部分木に存在する頂点の数字を並び替えた数列のパターン数です。
$dp[i]$ について考えるとき、子の数列それぞれの要素をいったん同じものとみなして並べ方を考え、最後に子の数列それぞれのパターン数をかければいいことになります。
子それぞれの数列を持ってきて、マージソートのようにしてマージするパターン数がわかれば、 $i$ の子の集合を $S$ として、
$(マージのパターン数) \times \prod_{j \in S}{dp[j]}$
となります。
マージのパターン数は、同じものを含む順列について考えていることになるので、

同じものがあるときの順列

ここを参考にすればよく、
$\displaystyle dp[i] = \frac{(c_{i}-1)!}{\prod_{j \in S}{c_{j}!}} \times \prod_{j \in S}{dp[j]}$
となります。
これで $k = 1$ の場合について解けました。
あとは全方位木DPを用いればよく、 $c,dp$ それぞれは和と積で構成されているので、今みている頂点から根を子へうつす際に、今見ている頂点についての値を、全頂点についての計算から、うつす子の値を除いたものに計算しなおせばよいです。