题目链接：

题意：

　　给你一棵树（编号从0到n-1，0为根节点），每个节点有黑白两种颜色，其中黑色节点有k+1个。

　　现在让你删掉k条边，使得这棵树变成k+1个连通块，并且要保证每个连通块中有且仅有一个黑色节点。

　　问你删边的方案有多少种。

 

题解：

　　表示状态：

　　　　dp[i][0/1] = numbers

　　　　表示在节点i所在的连通块中有(1)或没有(0)黑色节点时，节点i的子树的删边方法数

　　　　因为总要保证每个连通块中有且仅有一个黑点，所以最后一定删了恰好k条边，并不用记录当前删了多少边。

 

　　找出答案：

　　　　ans = dp[0][1]

　　　　最终根所在连通块中一定有且仅有一个黑点。

 

　　如何转移：

　　　　将删边的过程反过来考虑。

　　　　将节点i连向它的儿子的边一条条删去，相当于：

　　　　　　i本身没有儿子，然后将一棵棵子树添加为它的儿子，同时保证合法。

　　　　那么最终的方案取决于三个条件：

　　　　　　（1）i所在的连通块（简称块i）是否有黑点

　　　　　　（2）son所在的连通块（简称块son）是否有黑点

　　　　　　（3）是否删去边(i,son)

　　　　分情况讨论：

　　　　　　（1）块i有黑点

　　　　　　　　a. 块son有黑点，此时只能将边删去，最终的块i有黑点

　　　　　　　　b. 块son全是白，此时只能保留这条边，最终的块i有黑点

　　　　　　（2）i是白色

　　　　　　　　a. 块son有黑点，此时删边或不删都可以：

　　　　　　　　　　I. 删边，最终的块i全是白

　　　　　　　　　　II. 不删，最终的块i有黑点

　　　　　　　　b. 块son全是白，此时只能保留这条边，最终的块i全是白

　　　　综上：

　　　　　　dp[now][1] = dp[son][0]*dp[now][1] + dp[son][1]*(dp[now][1]+dp[now][0])

　　　　　　dp[now][0] = (dp[son][0]+dp[son][1])*dp[now][0]

 

　　边界条件：

　　　　dp[i][c[i]]=1

 

AC Code:

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define MAX_N 100005#define MOD 1000000007using namespace std;int n;int c[MAX_N];long long dp[MAX_N][2];vector
         
           edge[MAX_N];void read(){    cin>>n;    int x;    for(int i=1;i
          
           >x; edge[x].push_back(i); } for(int i=0;i
           
            >c[i]; }}void dfs(int now){ dp[now][c[now]]=1; for(int i=0;i