树形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
No comments:
Post a Comment