题目: LINK
给定一个树，每个节点是白色或者黑色。可以删去一个边的集合使得剩下来的每个树里面有且仅有一个节点是黑色的。求这样集合的数量。
显然是树形DP。 dp[n][2]， dp[i][j]代表到i这个点它所在的子树的划分情况都满足条件(每部分只有一个黑点)的情况，dp[i][0] 包含i节点的这部分没有黑点的集合数量，dp[i][1]表示这部分有一个黑点的集合数量。
对于每个节点，计算到它的一个子树(根节点v) (设连接的边为x)的时候，dp[i][0] 为dp[i][0] * dp[v][1] + dp[i][0] * dp[v][0], 已处理完的一定要取dp[i][0], 如果取x 则子树取dp[v][0],如果不取x, 则子树取dp[v][1].
dp[i][1] 为 dp[i][1] *(dp[v][0] + dp[v][1]) + dp[i][0] *dp[v][1] , 如果处理完的取dp[i][1],x取的话为dp[v][0], 不取的话为dp[v][1];
如果处理完的取dp[i][0], x一定要取且要乘以dp[v][1](ps: dp[v][0] 不能要，如果要的话 v 点的部分会出现不含黑点的情况)
#include
#include
#include
#include
#include
#include
#include
#include
#include 【Codeforces|Codeforces Round #263 (Div. 1) B. Appleman and Tree( 树形DP )】
推荐阅读
- codeforces B. Young Explorers
- codeforces C. Mere Array
- codeforces D. Omkar and Bed Wars
- codeforces C. Omkar and Waterslide
- codeforces B. Omkar and Infinity Clock
- codeforces B. Ternary Sequence
- 题目|C. Ayoub and Lost Array（思维dp）
- HDU 5185 Equation (DP)