51nod 1500 苹果曼和树【树形DP】

Description

苹果曼有一棵n个点的树。有一些（至少一个）结点被标记为黑色，有一些结点被标记为白色。

现在考虑一个包含k(0 ≤ k < n)条树边的集合。如果苹果曼删除这些边，那么会将这个树分成(k+1)个部分。每个部分还是一棵树。

现在苹果曼想知道有多少种边的集合，可以使得删除之后每一个部分恰好包含一个黑色结点。答案对1000000007 取余即可。

题解

定义f[i][0/1]$f[i][0/1]$表示以i$i$为根的子树，i$i$所在的块中没有/有黑点的方案数。

考虑如何合并两个子树的答案，可得，f[i][0]∗=f[son][0]+f[son][1];f[i][1]=f[i][0]∗f[son][1]+f[i][1]∗(f[son][0]+f[son][1])$f[i][0]*=f[son][0]+f[son][1];f[i][1]=f[i][0]*f[son][1]+f[i][1]*(f[son][0]+f[son][1])$;

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 100006
#define tt 1000000007
#define LL long long
using namespace std;
inline char nc(){
    static char buf[100000],*i=buf,*j=buf;
    return i==j&&(j=(i=buf)+fread(buf,1,100000,stdin),i==j)?EOF:*i++;
}
inline int _read(){
    char ch=nc();int sum=0;
    while(!(ch>="0"&&ch<="9"))ch=nc();
    while(ch>="0"&&ch<="9")sum=sum*10+ch-48,ch=nc();
    return sum;
}
int n,tot,a[maxn],lnk[maxn],nxt[maxn*2],son[maxn*2];
LL f[maxn][2];
bool vis[maxn];
void add(int x,int y){
    nxt[++tot]=lnk[x];son[tot]=y;lnk[x]=tot;
}
void dfs(int x){
    vis[x]=0;f[x][a[x]]=1;
    for(int j=lnk[x];j;j=nxt[j]) if(vis[son[j]]){
        dfs(son[j]);
        (f[x][1]=f[x][0]*f[son[j]][1]%tt+f[x][1]*(f[son[j]][0]+f[son[j]][1])%tt)%=tt;
        (f[x][0]*=(f[son[j]][1]+f[son[j]][0])%tt)%=tt;
    }
}
int main(){
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    n=_read();
    for(int i=1,x;i<n;i++)x=_read(),add(i,x),add(x,i);
    for(int i=0;i<n;i++)a[i]=_read();
    memset(vis,1,sizeof(vis));
    dfs(1);
    printf("%lld
",f[1][1]);
    return 0;
}