牛牛染颜色 （树形DP）

题目传送门

思路：

AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int mod=1e9+7,N=1e6+5;
typedef long long ll;
int dp[N][2],h[N],cnt=1;
struct edge{int to,nt;}e[N<<1];
void add(int u,int v){e[cnt]={v,h[u]},h[u]=cnt++;};
void dfs(int u,int fa){
	dp[u][0]=dp[u][1]=1;//初始化 
	for(int i=h[u];i;i=e[i].nt){
		int v=e[i].to;
		if(v==fa) continue;
		dfs(v,u);
		dp[u][0]=((ll)dp[u][0]+dp[v][0]+dp[v][1]-1)%mod;
		dp[u][1]=((ll)dp[u][1]*(dp[v][0]+dp[v][1]))%mod;
	}
}
int main(){
	int n;
	scanf("%d",&n);
	for(int i=2,u,v;i<=n;i++)
	scanf("%d%d",&u,&v),add(u,v),add(v,u);
	dfs(1,0);
	printf("%d\n",(dp[1][0]+dp[1][1])%mod);
	return 0; 
}