Appleman_and_Tree
Appleman and Tree
如果觉得我的题解看不懂可以去看 大佬的题解
题目大意
将一颗树节点染成白色或者黑色,减去几条变使得每个联通分支都有一个黑色节点,问有多少种减边方案。
题解
树状dp+dfs
下次看到两种状态加点的。dp应该想到用2维。
- 定义$dp[i][j]$表示点$i$在以点$i$为根的子树去掉点$i$所在的联通快有黑点$1$和无黑点$0$的方案数
- 假设点$u$,首先如果$u$是黑色,那么$$dp[i][1]=1$$,否则$dp[i][0]=1$。
- 点$u$加入一个子树$v$。假设原来$u$没有黑点。
- 如果加入的$v$是有黑点的,有两种选择,切断边$u$还是没有黑点,方案数$dp[u][0]=dp[u][0]*dp[v][1]$,不切断边$u$就产生了黑点$dp[u][1]=dp[u][0]*dp[v][1]$
- 如果加入的$v$是无黑点的,只能选择不切断。方案数$dp[u][0]=dp[u][0]*dp[v][0]$
- 点$$u$$加入一个子树$v$。假设原来$u$有黑点。
- 如果加入的$v$是有黑点的,只能选择切断,方案数$dp[u][1]=dp[u][1]*dp[v][1]$
- 如果加入的点$v$是无黑点的,只能选择切断,因为不能产生无黑点的联通分支,方案数$dp[u][1]=dp[u][1]*dp[v][0]$
- 点$u$加入一个子树$v$。假设原来$u$没有黑点。
1 |
|
Appleman_and_Tree
https://www.cheasim.com/acm/2018/08/19/Appleman-and-Tree.html