【Codeforces 461B】Appleman and Tree

mrsrz 11月 14, 2019

树形DP

题目大意：

给定一棵树，每个结点为黑色或白色。

现在可以切掉若干条边，要求满足切掉后的连通块中，每个连通块有且仅有一个黑色结点。

求方案数。

题解：

树形dp。

令 $f_{i,0/1}$ 表示子树 $i$ 中，与 $i$ 连通的那个连通块中有黑色结点/无黑色结点，其他部分已经合法的方案数。

没有黑色结点的连通块不能自己封闭，而有黑色结点的连通块不能再和黑色结点合并。

$f_{i,0}=f_{i,0}\times (f_{son,0}+f_{son,1})\\ f_{i,1}=f_{i,1}\times(f_{son,0}+f_{son,1})+f_{i,0}\times f_{son,1}$

第一行的意思是，当前结点不能有黑色结点的状态，对于当前结点的每棵子树，要么和没黑色结点的连通块合并，要么和有黑色结点的连通块切断。

第二行的意思是，当前结点有黑色结点的状态，对于当前结点的每棵子树，要么和没黑色结点的连通块合并，要么和有黑色结点的连通块切断。或者，从没有黑色结点的状态，通过和一个有黑色结点的连通块合并后得到。

时间复杂度 $O(n)$。

Code：

#include<iostream>
#include<cstdio>
using namespace std;
const int md=1e9+7,N=1e5+6;
typedef long long LL;
int n,f[N][2],fa[N],head[N],cnt,col[N];
struct edge{
    int to,nxt;
}e[N];
void dfs(int now){
    f[now][col[now]]=1;
    for(int i=head[now];i;i=e[i].nxt){
        dfs(e[i].to);
        f[now][1]=((LL)f[now][1]*(f[e[i].to][0]+f[e[i].to][1])+(LL)f[now][0]*f[e[i].to][1])%md;
        f[now][0]=(LL)f[now][0]*(f[e[i].to][0]+f[e[i].to][1])%md;
    }
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=2;i<=n;++i){
        cin>>fa[i],++fa[i];
        e[++cnt]=(edge){i,head[fa[i]]},head[fa[i]]=cnt;
    }
    for(int i=1;i<=n;++i)
        cin>>col[i];
    dfs(1);
    cout<<f[1][1]<<'\n';
    return 0;
}