Codeforces Round #263 (Div.1) B. Appleman and Tree
浏览数：71 /
时间：2015年06月11日
题目地址：http://codeforces.com/contest/461/problem/B
题目大意：给一棵树，每个点为白色或黑色，切断一些边，使得每个连通块有且仅有一个黑点，问划分方案数。
算法讨论：TreeDP。f[x][0..1]表示x所在连通块有0/1个黑点。设y为x的儿子，则DP方程为f[x][1]=f[x][1]*f[y][0]+f[x][1]*f[y][1]+f[x][0]*f[y][1],f[x][0]=f[x][0]*f[y][0]+f[x][0]*f[y][1]。
Code:
#include <cstdio>
#define N 100000
#define mod 1000000007
using namespace std;
long long f[N+10][2];
int n,x,mm,next[N+10],son[N+10],ed[N+10],c[N+10];
inline void add(int x,int y){
next[++mm]=son[x],son[x]=mm,ed[mm]=y;
}
void dfs(int x){
f[x][c[x]]=1;
for (int i=son[x];i;i=next[i]){
int y=ed[i];
dfs(y);
f[x][1]=(f[x][1]*f[y][0]%mod+f[x][1]*f[y][1]%mod+f[x][0]*f[y][1]%mod)%mod;
f[x][0]=(f[x][0]*f[y][0]%mod+f[x][0]*f[y][1]%mod)%mod;
}
}
int main(){
scanf("%d",&n);
for (int i=2;i<=n;++i) scanf("%d",&x),add(++x,i);
for (int i=1;i<=n;++i) scanf("%d",&c[i]);
dfs(1);
printf("%I64d\n",f[1][1]);
return 0;
}
By Charlie Pan
Aug 27,2014
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
