树形DP | dtyfc

树形DP。

定义dp[x][0]表示切割后，以x为根的子树没有黑点的方案数，dp[x][1]表示切割后以x为根的子树有一个黑点的方案数。然后我们任选一个点作为根开始dfs，然后从下至上更新每个节点的信息。

如果x这个点本身就是黑点，那么dp[x][0]没有意义，只考虑dp[x][1]。设x的一个儿子是u，假设我们切断了(x, u)这条边的话，那么方案数就应该有dp[x][1] * dp[u][1]，因为切断之后它的儿子所在的块内必须有黑点；如果不切断的话，那么方案数有dp[x][1] * dp[u][0]，因为不切断的话，自己本身是黑点，就不允许儿子所在的子数中有黑点。所以对于每一个u，dp[x][1] *= (dp[u][0] + dp[u][1])。

如果x这个点是一个白点的，同样地，我们考虑它和它的一个儿子u之间的边(u, v)。先考虑dp[x][0]和如更新，如果切断这条边，那么儿子所在的子树必须有黑点，方案数有dp[x][0] * dp[u][1]；如果不切割，因为dp[x][0]表示以x为根的的子树中没黑点，所以u为根的子树中一定也不能有黑点，方案数有dp[x][0] * dp[u][0]。所以dp[x][0] *= (dp[u][0] + dp[u][1])。再考虑如何更新dp[x][1]，因为x本身是一个白点，所以它的子树中必定有黑点。我们同样考虑(u, x)这条边切不切，会得到dp[x][1] * (dp[u][0] + dp[u][1])的方案，与之前不同的是，如果不切的话，还会有额外的方案数dp[x][0] * dp[u][1]，表示以之前的儿子为根的子树里都是白点，以u为根的子树里有黑点的方案。即dp[x][1] = dp[x][0] * dp[u][1] + dp[x][1] * (dp[u][0] + dp[u][1])。

最后的方案数就是dp[root][1]，因为他是这棵树的树根，切割之后他一定属于某个包含黑点的块里，所以子树必须有一个黑点。

Read full article from 树形DP | dtyfc