题意

将一个有 $N$ 个点的树染上颜色，可染黑白两种颜色，但两个相邻的点不能同为黑色，求染色方法总数。

思路

我们让 $dp_{i,j}$ 表示为当前情况下染色方法数，其中 $i$ 表示节点的编号， $j$ 表示为节点的颜色（ $0$ 为黑色， $1$ 为白色）。我们使 $1$ 为根节点（其实其他也行）。所以答案表示为 $(dp_{1,0} + dp_{1,1})$ 。

设节点 $y$ 是节点 $x$ 的子节点 ,则状态转移方程为

$$\left\{ \begin{array}{l} f_{x,0} = \prod (f_{y,0} + f_{y,1})\\ f_{x,1} = \prod f_{y,0} \end{array} \right.$$

很好理解。

当当前节点为黑色，其子节点必须为白色，所以只有子节点为白色的情况数能做出贡献。

而当当前节点为白色时，其子节点颜色无所谓，所以子节点黑白两种颜色的情况数均能做出贡献。

什么？你问我为什么要从下至上计算？因为从上至下太麻烦了。如果那样做，最后还要统计叶子节点的总情况数。而从下至上答案就为根节点的情况数。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int N=1e6+10,P=1e9+7;
ll a[N],dp[N][2],cnt[N],n,m,x,y;
bool v[N];
vector<ll>G[N];
void dfs(int x){
	dp[x][0]=dp[x][1]=1;
	//两种涂色方法都可自成一种
	//(防止未初始化而所有点的方案数乘起来还是个0,则遍历无效) 
	for(ll y:G[x])if(!v[y])//y点还没被染色 
	{
		v[y]=1;dfs(y);//标记染过,遍历下去 
		dp[x][0]*=dp[y][0]+dp[y][1],dp[x][0]%=P;
		//这个点染白色旁边是黑点或白点都可以 
		dp[x][1]*=dp[y][0],dp[x][1]%=P;
		//但染黑色旁边就只能是白点 
	}
}
int main(){
	scanf("%lld",&n);
	for(ll i=1,x,y;i<n;i++){
		scanf("%lld%lld",&x,&y);
		G[x].push_back(y),G[y].push_back(x);
		//构图 
	}
	v[1]=1;dfs(1);
	printf("%lld\n",(dp[1][0]+dp[1][1])%P);
	//第1个点染成白色和黑色是两种不同情况,要相加 
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7;
vector<int> G[N];
long long f[N][2];
void dfs(int x, int xfa)
{
    f[x][0] = f[x][1] = 1;
    for (int y : G[x]) if (y != xfa)
        {
            dfs(y, x);
            f[x][0] *= f[y][0] + f[y][1], f[x][0] %= mod;
            f[x][1] *= f[y][0], f[x][1] %= mod;
        }
}
int main()
{
    int n; cin >> n;
    for (int i = 1, x, y; i < n; i++)
        cin >> x >> y,
        G[x].push_back(y),
        G[y].push_back(x);

    dfs(1, 0);

    cout << (f[1][0] + f[1][1]) % mod << '\n';
    return 0;
}