树形dp CF461B Appleman and Tree

Appleman and Tree

大意：
 

给你一棵有 n 个节点的树，下标从 0 开始。

第 i 个节点可以为白色或黑色。

现在你可以从中删去若干条边，使得剩下的每个部分恰有一个黑色节点。

问有多少种符合条件的删边方法，答案对 10^9+7取模。

思路：
首先很明显用dp

状态怎么设？不妨先考虑dp[i]表示以i为根的子树，满足条件的删边方法数。但是很快就会发现这种状态表示是不够合理的，因为无法仅靠这一个状态就完成转移

那就加状态。怎么加？

我们会发现一个合法状态（联通块内有且只有一个黑点）可以由两个合法状态切割而成，也可以由一个合法状态与一个非法状态（没有黑点）合并而成。所以我们可以设dp[i][j]表示以i为子树的根，满足i所在的连通块由一个黑点的方案数（dp[i][1]）,和满足i所在的连通块由没有黑点的方案数（dp[i][0]）.至于多个黑点的情况，则可以由该dp式分割转移

考虑初始化：dp[i][color[i]]=1; 显然

考虑转移：

dp[id][1]=(dp[id][1]*dp[y][1]%mod+dp[id][1]*dp[y][0]%mod+dp[id][0]*dp[y][1]%mod)%mod;
       //父合法，儿合法，要分开    //父合法，儿非法         //父非法，儿合法
dp[id][0]=(dp[id][0]*dp[y][0]%mod+dp[id][0]*dp[y][1]%mod)%mod;
       //父，儿都非法（无黑点）    //父合法，儿非法，要分开

其实就是考虑所有情况，普通的组合计数就好了

知道dp之后这题也就很轻松了，但还是放一下代码

code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+7;
const ll N=1e5+10;
struct ty{
	ll t,l,next;
}edge[N<<1];
ll cn=0;
ll head[N];
ll n;
ll a,b;
ll mas[N];
void add(ll a,ll b,ll c)
{
	edge[++cn].t=b;
	edge[cn].l=c;
	edge[cn].next=head[a];
	head[a]=cn;
}
ll siz[N],dp[N][3];

void dfs(ll id,ll p)
{
	for(int i=head[id];i!=-1;i=edge[i].next)
	{
		ll y=edge[i].t;
		if(y==p) continue;
		dfs(y,id);
		dp[id][1]=(dp[id][1]*dp[y][1]%mod+dp[id][1]*dp[y][0]%mod+dp[id][0]*dp[y][1]%mod)%mod;
		dp[id][0]=(dp[id][0]*dp[y][0]%mod+dp[id][0]*dp[y][1]%mod)%mod;
		
	}
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	memset(head,-1,sizeof head);
	cin>>n;
	for(int i=1;i<n;++i)
	{
		cin>>a;
		a++;
		add(i+1,a,1);
		add(a,i+1,1);
	}
	for(int i=1;i<=n;++i) cin>>mas[i],dp[i][mas[i]]=1;
	dfs(1,-1);
	cout<<dp[1][1]<<endl;
	return 0;
}