锐客网

  1. 首页 > 睿知 > it技术 > >

CodeForces 461B Appleman and Tree（Tree dp）

IT知识codeforces

蹉跎莫遣韶光老，人生唯有读书好。这篇文章主要讲述CodeForces 461B Appleman and Tree：Tree dp相关的知识，希望能为你提供帮助。
题目链接：http://codeforces.com/problemset/problem/461/B
题意：
给你一棵树（编号从0到n-1，0为根节点），每个节点有黑白两种颜色，其中黑色节点有k+1个。
现在让你删掉k条边，使得这棵树变成k+1个连通块，并且要保证每个连通块中有且仅有一个黑色节点。
【CodeForces 461B Appleman and Tree（Tree dp）】问你删边的方案有多少种。
 
题解：
表示状态：
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 < iostream> #include < stdio.h> #include < string.h> #include < vector> #define MAX_N 100005 #define MOD 1000000007using namespace std; int n; int c[MAX_N]; long long dp[MAX_N][2]; vector< int> edge[MAX_N]; void read() { cin> > n; int x; for(int i=1; i< n; i++) { cin> > x; edge[x].push_back(i); } for(int i=0; i< n; i++) { cin> > c[i]; } }void dfs(int now) { dp[now][c[now]]=1; for(int i=0; i< edge[now].size(); i++) { int temp=edge[now][i]; dfs(temp); long long blk=dp[now][1]; long long wht=dp[now][0]; dp[now][1]=(dp[temp][0]*blk+dp[temp][1]*(blk+wht))%MOD; dp[now][0]=(dp[temp][0]+dp[temp][1])*wht%MOD; } }void work() { dfs(0); cout< < dp[0][1]< < endl; }int main() { read(); work(); }

 

    推荐阅读


    上一篇：dubbo:application

    下一篇：移动端测试===Android内存泄露和GC机制（转）