Codeforces 461B Appleman and Tree

题意

给你一颗树，上面有黑色节点，也有白色节点，现在你要做的事情是，在这棵树上选出几条边，去掉，这样的话这棵树就会变成好多小树，这些小树一定要含且只含一个黑色点。问你有多少种不同的方法删边来满足要求。

思路

树形DP。往DP方面去想是因为原始的大问题可以进行剖分，即如果我们想要知道将整棵树按要求切割的方案个数，我们可以去考虑它的子树按要求切割的方案个数，对于子树也是同样地进行剖分。确定了将问题剖分的方向之后，就是确定状态了。

我们发现，要想从一颗树的子树的分割情况得到整棵树的分割情况，我们不仅要知道子树符合要求的分割情况，也要知道子树不符合要求的分割情况，这样才能覆盖全部情况。因此我们设定状态为，其中存值为将以为根节点的子树进行分割，而且与当前的子树根节点相连的节点中没有黑色节点方法个数；存值为将以为根节点的子树进行分割，而且与当前的子树根节点相连的节点中有且仅有一个黑色节点方法个数。

这里一定要清楚，0/1表示的是与根节点联通的节点中是不是有黑色的节点，已经断开的地方，我们不用关心。

接下来讨论状态的转移：

• 如果当前节点已经是叶子节点，节点编号是：
  • 如果是黑色节点：
    • 因为黑色节点为根部的子树不可能不含有黑色节点。
    • 因为只有黑色节点一个点，只有一种分割方式就是把节点自己当作一颗树。
  • 如果是白色节点：
    • 因为白色叶子节点的子树中只有他自己一个白色节点，不可能含有黑色节点了，分割方式也只有一种就是把自己当成子树。
    • 因为白色叶子节点的子树中不可能含有黑色节点。
• 如果当前节点不是叶子节点，节点编号是，它的孩子节点们的编号为b_{i}：
  • 如果是白色节点：
    •  ，我们逐一检查每一个孩子节点，我们想得到的结果是当前节点直接相连的联通块里面不存在黑色节点，那么：
      • 如果当前检查的孩子节点是黑色的，我们考虑切开还是不切开同这个孩子节点连接的边：
        • 不切开的话，要求连接的孩子部分一定不可以有黑色节点，这显然是不可能的，不过黑色节点的始终是0，所以没关系。
        • 切开的话，就要求切开之后的孩子部分自己可以满足要求，这样的话有种方法。
      • 如果当前检查的孩子节点是白色的，我们考虑切开／不切开同孩子连接的边：
        • 切开的话，孩子部分自己要满足要求，这样的话有种方法。
        • 不切开的话，孩子部分与根节点直接相连的部分一定不可以包含黑色节点，这样的话有种方法。
    •  ，这个方程的计算必须和上面的同步进行。这个有一点不好懂，其实可以这么想：
      • 这一部分，我们要想的过程是将一个已经连接好了黑点的根部，讨论是不是要和当前的孩子相连的过程：
      • 如果当前检查的节点是黑色节点，我们还是考虑切开／不切开：
        • 不切开的话不满足要求，不过黑色节点的始终是0，所以没关系。
        • 切开的话，连接上去的孩子部分一定要满足要求，有且只有一个黑点，所以有种方法。
      • 如果当前检查的是白色节点，切开／不切开：
        • 不切开的话，还是不满足要求，但是如果这个时候在根节点上已经有带黑点的联通块连上去了，这个时候只要令连接上去的部分没有黑点就可以了，所以有种方法。
        • 切开的话，孩子部分要自己保持成立，有且只有一个黑点，所以有种方法。
      • 而这一部分，想法是当前依然不成立的根部，和带有一个黑点的孩子部分连接。
  • 如果是黑色节点：
    • 因为黑色节点为根部的子树不可能不含有黑色节点
    • 我们逐一检查每一个孩子节点，既然我们想得到的结果是当前节点直接相连的联通块里面只有一个黑色节点，那么：
      • 如果当前检查的孩子节点是黑色的，我们考虑切开还是不切开同这个孩子节点连接的边：
        • 切开的话，没有问题，因为当前考虑的子树的根节点已经是黑的了，而且还要让让切开之后切出来的孩子的那一部分保持成立，要想做到这一点的话有种方法。
        • 不切开的话，显然是不行的，因为这样就有了两个黑色节点，不过黑色节点的始终是0，所以加进去也没关系。
      • 如果当前检查的孩子节点是白色的，我们考虑切开／不切开同孩子连接的边：
        • 切开的话，还要保证切除的孩子部分也成立，因此孩子部分有种方法。
        • 不切开的话，因为当前节点是黑色的，链接孩子节点之后，连接上的部分不可以含有黑色节点，孩子节点能做到这样的方法有种。

写了一堆废话其实就是为了理清思路，思维能力太弱只能这样了。DP的思路搞定之后，具体的操作就非常简单，利用DFS深入叶子，在返回的过程中进行对孩子的考察和对自身的更新，最后在根节点上读取答案。

代码