[NFLS 1436/6] 子树 题解

题意

给定一棵 $n$ 个节点的树, 可以从中选出一些节点, 这些节点是连通的, 构成一棵
子树. 求所有子树方案的节点数目的总和.

题解

设 $g(u)$ 以 $u$ 为根的方案总数.

设 $h(u)$ 以 $u$ 为根的方案总和.

$$g(u) = \prod_{v \in son(u)} g(v) \newline h(u) = \sum_{v \in sum(u)} \frac{g(u)}{g(v)} h(v) \newline res = sum(h(u))$$

证明

$$h(v) = c_{1, 1} + c_{1, 2} + c_{1, 3} + ... \newline h(u) = (c_{1, 1} + c_{2, 1}) + (c_{1, 2} + c_{2, 2}) + ...$$

$c_{1, 1}, c_{1, 2} ...$ 出现了 $\frac {g_u} {g_v}$ 次,
其他同理.