题意
给定一棵 \(n\) 个节点、以 \(1\) 为根的树。对于每一条边，可以选择保留或不保留。定义一个方案的权值是只看保留的边时，形成的各个连通块大小之积。试计算 \(2^{n-1}\) 种方案的权值之和。答案对 \(998244353\) 取模。
解答
设 \(f_{i, j}\) 表示根为 \(i\) 的子树中，根所在连通块大小为 \(j\) 的所有方案的权值和（乘的时候不乘 \(j\)）。
考虑 \(f_i\) 的生成函数 \(F_i\)，即 \(F_i(x) = \sum\limits_{j = 0}^{siz_i} f_{i, j}x^j\)（这里 \(j=0\) 时在点 \(i\) 上方截断，反之 \(i\) 则与其父亲在同一连通块）.
那么有 \(F_u(x) = x\prod\limits_{v \in son_u} F_v(x) + F_u'(1)\).
其中
\[\begin{split} F_u'(x) &= \left(x\prod\limits_{v \in son_u} F_v(x)\right)' \\ &= \prod\limits_{v \in son_u} F_v(x) + x\left(\prod\limits_{v \in son_u} F_v(x)\right)'\\ &= \prod\limits_{v \in son_u} F_v(x) + x\left(\prod\limits_{v \in son_u} F_v(x)\right)\left(\sum_{v\in son_u} \frac{F_v'(x)}{F_v(x)}\right) \end{split} \]对每个 \(p\) 存储 \(F_p(1), F_P'(1)\)，树形 dp 即可。
最终的转移方程为：
\[\begin{split} F_u(1) &= 2\prod\limits_{v \in son_u} F_v(1) + \prod\limits_{v \in son_u} F_v(1)\left(\sum_{v\in son_u} \frac{F_v'(1)}{F_v(1)}\right)\\ F_u'(1) &= \prod\limits_{v \in son_u} F_v(1) + \prod\limits_{v \in son_u} F_v(1)\left(\sum_{v\in son_u} \frac{F_v'(1)}{F_v(1)}\right) \end{split} \]本题思路妙在生成函数，令人回味无穷。
标签：right,limits,sum,son,gf,树形,prod,dp,left From： https://www.cnblogs.com/0922-Blog/p/TreeDPwithGF.html