ここで、異なる操作(の集合)は異なる終状態に対応するので(深さが大きい方の頂点から考えることでわかります)、ありうる操作の集合を考えればよいです。 操作列に対して数え上げがより容易な一対一対応を構成します。

操作は dfs の post-order 順に行っていくものとしてよいです。ここで、非負整数列 \((A_i)\) の代わりに、各頂点には \(A_i\) 個のボールが一列に並んでいるものとします。

以下のようなボールに印をつけるルールを考えます。

はじめ、\(\sum_i A_i\) 個のボールのうちいくつかには印がついている。

頂点を post-order 順に処理する。頂点 \(i\) のボールの列のうち、最も右側にある印のついたボールが \(B_i\) 個目であるとする。(存在しない場合は \(0\))

選んだ \(B_i\) 個のボールを左から順番に \(r\) 個ずつに複製し、\(P_i\) の頂点のボールの列に右から加える。印がついているボールを複製したときは \(r\) 個のうち \(1\) つ以上 \(r\) 個以下のボールにも印をつける。ただし、\(B_i\) 個目のボールは \(0\) 個でもよい。

この操作を繰り返し、最終的に印の付いたボールが \(0\) 個になるような操作列は、元の操作列と一対一対応している。

これは、元の操作列から印をつける操作が復元できることを示せばよい。post-order の逆順に頂点を処理し、複製したボールのうち最も右側のボールに印をつけ、また印は複製元に戻すときに伝搬するものとすれば良い。

よって、最終的に印がなくなるような印のつけ方(元の \(\sum A_i\) 個と複製したときの双方)の場合の数がわかれば良い。

印の付いていないボールは無視してよい。また、印が減る操作は高々 \(N-1\) 回しか行われないことから、各頂点に存在する印の数は \(N - 1\) 個以下ともしてよい。

元の \(A_i\) 個のうち \(K\) 個に印をつける場合の数は簡単にわかり、複製されるときの数も \((\binom{r}{1} x + \binom{r}{2} x^2 + \ldots + \binom{r}{r} x^{r })^K\) を \(K = 1, \ldots, N - 1\) について、\(N-1\) 次まで前計算しておけばよい。 後は、木 dfs をしながら、(印の数, 場合の数) を持った配列を畳み込めばよい。

計算量は複製するパートがボトルネックになり、 \(O(N^3)\) となる。