Appleman and Tree

题意:n个点的树,其中k个点颜色为黑,其余为白,求有多少种划分分方法使得k个子树的森林,每个树上恰好有一个黑点

分析:显然,树dp,每个点有两种状态,已经属于某个点的和还不属于某个点的该子树的划分状态,想了想,可以这么搞

dp[i][0],表示该点不属于一个黑点的划分 ,初始为黑点为0,白点为1

dp[i][1],表示该点属于一个黑点的划分,初始为黑点为1,白点为0

dp[u][0]=dp[u][0]*(dp[v][0]+dp[v][1])v是u的儿子

dp[u][1]=dp[u][1]*(dp[v][0]+dp[v][1])+dp[u][0]*dp[v][1]

意思不难理解,挺不错的一道题,实现没有难度,注意取模就好了

原文地址:https://www.cnblogs.com/jihe/p/5802982.html