Codeforces Round #263 Div.1 B Appleman and Tree --树形DP【转】
2024-10-13 08:39:04
题意:给了一棵树以及每个节点的颜色,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]
代码:
#include <iostream>
#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#define Mod 1000000007
#define lll __int64
using namespace std;
#define N 100007 vector<int> G[N];
lll dp[N][];
int col[N]; void dfs(int u,int fa)
{
dp[u][] = 1LL;
dp[u][] = 0LL;
for(int i=;i<G[u].size();i++)
{
int v = G[u][i];
if(v == fa) continue;
dfs(v,u);
dp[u][] = (dp[u][]%Mod*dp[v][]%Mod);
dp[u][] = (dp[u][]%Mod + dp[u][]*dp[v][]%Mod)%Mod;
dp[u][] = dp[u][]%Mod*dp[v][]%Mod;
}
if(col[u] == ) dp[u][] = dp[u][];
else dp[u][] = (dp[u][]+dp[u][])%Mod;
} int main()
{
int n,x,i;
while(scanf("%d",&n)!=EOF)
{
for(i=;i<=n;i++)
G[i].clear();
for(i=;i<n-;i++)
{
scanf("%d",&x);
G[i+].push_back(x);
G[x].push_back(i+);
}
for(i=;i<n;i++)
scanf("%d",&col[i]);
dfs(,-);
printf("%I64d\n",dp[][]%Mod);
}
return ;
}
最新文章
- WPF中Popup的几个问题
- OpenGl在VS中的配置
- 【转】HideInInspector 与SerializeField
- Linux系统下给VMWare安装Tools
- cocos2d-x触屏事件(单点触屏)
- PHP 文件上传注意一个地方,移动文件时要保证目标目录存在,否则报错
- 获取FMS的状态信息
- linux 管道通信
- javascript 实现页面显示当前时间 动态读秒
- mybatis执行批量更新数据
- 解题:BZOJ 2989 数列
- 第11月第8天 ffmpeg ffplay
- linux学习笔记-12.输入输出重定向及管道
- 在IIS服务器上屏蔽IP的访问
- 通过unixODBC访问PostgreSQL数据库
- 集成学习AdaBoost算法——学习笔记
- 项目实战:BBS+Blog项目开发
- Create process in UNIX like system
- 团队的初体验与Scrum的初识
- HDU 1159 Common Subsequence(POJ 1458)