洛谷题面
感觉是非常经典的一道题,最近好像总是见到,今天也算给它做了,发一篇题解来记录一下。
这道题是一道树形 DP 题,设 f [ u ] [ 0 / 1 ] f[u][0/1] f[u][0/1] 表示 u u u 点属于一个无黑点 / / / 有且仅有一个黑点的联通块时的方案数。我们考虑如何进行转移。
对于 f [ u ] [ 1 ] f[u][1] f[u][1],我们考虑如果 u u u 在一个有且仅有一个黑点的联通块时,对于它的儿子 v v v,有三种情况:
- 儿子是不合法的,那么我们需要把儿子和 u u u 放在一个联通块里,也就是儿子要贴着父亲,对应的贡献是 f [ u ] [ 1 ] × f [ v ] [ 0 ] f[u][1] \times f[v][0] f[u][1]×f[v][0]。
- 儿子是合法的,那么我们可以从中间断开,对应的贡献是 f [ u ] [ 1 ] × f [ v ] [ 1 ] f[u][1] \times f[v][1] f[u][1]×f[v][1]。
- 父亲是不合法的,那么需要把 u u u 和它的儿子放到一个联通块里,对应的贡献是 f [ u ] [ 0 ] × f [ v ] [ 1 ] f[u][0] \times f[v][1] f[u][0]×<