小红拿到了一棵树,初始所有节点都是白色。
小红希望染红若干个节点,使得不存在两个白色节点相邻。
小红想知道,共有多少种不同的染色方案?
由于答案过大,请对 109+7 取模。
第一行输入一个正整数 n,代表节点数量。
接下来的 n−1 行,每行输入两个正整数 u,v ,代表节点 u 和节点 v 有一条边连接。
1≤n≤105,1≤u,v≤n
一个整数,代表染色的方案数。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define llinf 0x3f3f3f3f3f3f3f3f
#define inf 1175111725
int t,n,m,f[200007];
ll r[200007],w[200007],mod=1000000007;
vector<int>v[200007];
void C(int x){
//cout<<x<<endl;
f[x]=1;
r[x]=w[x]=1;
for(int i=0;i<v[x].size();i++){
if(f[v[x][i]]) continue;
C(v[x][i]);
r[x]=(r[x]*(r[v[x][i]]+w[v[x][i]]))%mod;
w[x]=(w[x]*r[v[x][i]])%mod;
}
return;
}
int main(){
cin>>n;
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
C(1);
cout<<r[1]+w[1];
return 0;
}