题目描述

给定包含n个节点的树，每个节点具有颜色0或颜色1。求其有多少连通子图，满足度数为1的节点颜色相同。

解析

因为是连通数，且是计数。这里暴力明显不行所以首选dp。样例下图：
alt
不难看出是树状dp。所以我们这里可以考虑DPx,c(x为当前节点，c为x的01取值) 拿样例来说：根节点1有 Son2 和 Son3 然后DP1,c的总数就是 (DP2,c)+1乘(DP3,c)+1。+1是有一种不选择的情况。具体看代码注释。

直接上代码

#include<bits/stdc++.h> 
using namespace std;
int n;
int col[300004];
long long dp[300005][5] ;
char s[300005];
vector<int> Vr[300005];
const long long mod=1e9+7;
long long cnt=0;//最终答案 
void _Zl(int x,int y)//x是当前的根,y是他的父亲 
{
	dp[x][0]=1;//假如x颜色是1则是 不选择  的那一种情况，否则是 选择 
	dp[x][1]=1;//假如x颜色是1则是 选择  的那一种情况，否则是 不选择 
	int bt; 
	long long ans1=0,ans2=0;//用来累加1的总和 和 0的总和 
	for(int i=0;i<Vr[x].size();i++) //查找Vr[x]的连通边 
	{
		bt=Vr[x][i];//取出x的一条连通边
		if(bt==y)  continue;//判断是否往回找防止死循环
		_Zl(bt,x);//从合法的边开始向下查询
		dp[x][1]=(1ll*dp[x][1]*(dp[bt][1]+1))%mod;
		//连乘 x的儿子的方案数量 因为有“_Zl ”所以下面的子节点的方案书都存到father上 所以只需要x乘上儿子就行 
		dp[x][0]=(1ll*dp[x][0]*(dp[bt][0]+1))%mod;
		//“dp[bt]([0]or[1])+1”是儿子的方案书加上 不选择 的一种 方案 
		ans1=(ans1+dp[bt][1])%mod;//让树的连通的 
		ans2=(ans2+dp[bt][0])%mod;
	}
	if(col[x]==1) 
	{
		dp[x][0]--;//本身不能算上
		cnt=(cnt+dp[x][1])%mod;//当他x为1合法的时候cnt加上以x为跟的1的总和 
		cnt=(cnt-ans2+dp[x][0])%mod;//将取0时 不合法的总方案数都去除 留下儿子方案数 
	}
	else
	{
		dp[x][1]--;
		cnt=(cnt+dp[x][0])%mod;
		cnt=(cnt-ans1+dp[x][1])%mod;
	}
}
int main(){
	scanf("%d",&n);//输入，这里也可以选择 快读 
	scanf("%s",&s);//输入 
	for(int i=0;i<n;i++)
	{
		col[i+1]=s[i]-'0';//将字符串改为数字存 
	}
	int x,y;
	for(int i=1;i<n;i++)
	{
		scanf("%d %d",&x,&y);//输入
		Vr[x].push_back(y);//x边可以连通y 
		Vr[y].push_back(x);//y边可以连通x 
	}
	_Zl(1,1);//从根开始 father定义为1也是为了防止回溯 
	printf("%lld\n",(cnt%mod+mod)%mod);//取模后输出 +mod是为了防止负数 
}
	
	
	
	
	
	 js