CF461B Appleman and Tree题解

洛谷题面

感觉是非常经典的一道题，最近好像总是见到，今天也算给它做了，发一篇题解来记录一下。

这道题是一道树形 DP 题，设 $f[u][0/1]$ 表示 $u$ 点属于一个无黑点 $/$ 有且仅有一个黑点的联通块时的方案数。我们考虑如何进行转移。

对于 $f[u][1]$，我们考虑如果 $u$ 在一个有且仅有一个黑点的联通块时，对于它的儿子 $v$，有三种情况：

1. 儿子是不合法的，那么我们需要把儿子和 $u$ 放在一个联通块里，也就是儿子要贴着父亲，对应的贡献是$f[u][1]\times f[v][0]$。
2. 儿子是合法的，那么我们可以从中间断开，对应的贡献是 $f[u][1]\times f[v][1]$。
3. 父亲是不合法的，那么需要把 $u$ 和它的儿子放到一个联通块里，对应的贡献是 $f[u][0]\times$