Codeforces Round #263 (Div.1) B. Appleman and Tree Codeforces

题目地址：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 #define N 100000 #define mod 1000000007using 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
【Codeforces Round #263 (Div.1) B. Appleman and Tree】Aug 27,2014