# yukicoder No.2214 Products on Tree ユーザー解説

[yukicoder No.2214 Products on Tree](https://yukicoder.me/problems/no/2214) のユーザー解説です。

:::info
積の和典型を経由せず、自然なDPの定義を母関数を用いて整理することで、機械的に処理する方法を紹介します。
:::

木DPで答えを求めることを考えましょう。全体の根を頂点 $r$ に取ります。部分木に含まれる辺を自由に切ったときの答えを計算できれば良いですが、部分木の根を含む連結成分の大きさが変化することがあり、都合が悪いです。

そこで、計算量のことを忘れて、次のようなDPを定義してみます：

$dp[v][s]$ : 頂点 $v$ を根とする部分木の辺を自由に切って、$v$ を含む連結成分の大きさが $s$ になるようなすべての方法に渡る、「$v$ を含む連結成分以外の連結成分の大きさの積」の総和。

$v$ を根とする部分木に $v$ の子として新たに $u$ を根とする部分木が加わるときの遷移式は、

$v-u$ 辺を切る場合が

$$dp[v][s]\xleftarrow{+}dp[v][s]\times s' dp[u][s']$$

となり、切らない場合が

$$dp[v][s+s'] \xleftarrow{+} dp[v][s] \times dp[u][s']$$

となります。母関数を用いて式を整理します。 $f_v=\sum_{s} dp[v][s] x^s$ とすると、

$$f_v\leftarrow f_v \times (f_u + f'_u(1))$$

です。ここで $f'$ は $df/dx$ のことです。

求める答えは $f'_r(1)$ です。そこで $f'_v(1)$ だけで遷移式が完結するかを検討します。

$$\begin{align}f'_v(1)&\leftarrow \dfrac{d}{dx}\left(f_v \times (f_u + f'_u(1))\right)(1)\\
&=f'_v(1)\times (f_u(1)+f'_u(1))+f_v(1)\times f'_u(1)\end{align}$$

となり、 $f_v(1)$ も必要になってしまいました。では、 $f_v(1)$ も含めるとどうでしょうか。

$$f_v(1) \leftarrow f_v(1)\times (f_u(1)+f'_u(1))$$

となり、$f_v(1),f'_v(1)$ だけで完結した遷移式が得られました。これは、DPの際に $dp[v][s]$ をすべて持つ必要がなく、結局 $f_v(1),f'_v(1)$ のみを持てば計算ができるということを意味します。

計算量は公式解説と同じく線形時間です。