锐客网

  1. 首页 > it技术 > >

Codeforces|Codeforces Round #263 Div.1 B Appleman and Tree --树形DP【转】

题意：给了一棵树以及每个节点的颜色，1代表黑，0代表白，求将这棵树拆成k棵树，使得每棵树恰好有一个黑色节点的方法数
解法：树形DP问题。定义：
dp[u][0]表示以u为根的子树对父亲的贡献为0
dp[u][1]表示以u为根的子树对父亲的贡献为1
现在假设u为白色，它的子树有x，y，z，那么有
dp[u][1]+=dp[x][1]*dp[y][0]*dp[z][0]+dp[x][0]*dp[y][1]*dp[z][0]+dp[x][0]*dp[y][0]*dp[z][1]
dp[u][0]+=dp[x][0]*dp[y][0]*dp[z][0]
然后判断u的颜色，假设u的父亲为p
1.为黑色，不切断边（u，p），那么dp[u][1]=dp[u][0]，切断（u，p），那么dp[u][0]不变
2.为白色，如果切断（u，p），dp[u][0]还要加上dp[u][1]

代码：
Codeforces|Codeforces Round #263 Div.1 B Appleman and Tree --树形DP【转】
文章图片
Codeforces|Codeforces Round #263 Div.1 B Appleman and Tree --树形DP【转】
文章图片

#include #include #include #include #include #include #include #include #include #define Mod 1000000007 #define lll __int64 using namespace std; #define N 100007vector G[N]; lll dp[N][2]; int col[N]; void dfs(int u,int fa) { dp[u][0] = 1LL; dp[u][1] = 0LL; for(int i=0; i
View Code
【Codeforces|Codeforces Round #263 Div.1 B Appleman and Tree --树形DP【转】】转载于:https://www.cnblogs.com/whatbeg/p/3941805.html

    推荐阅读


    上一篇：jQuery.ProgressBar|jQuery.ProgressBar 使用示例

    下一篇：断舍离整理升级篇