Independent Set
给一棵树,每一个点可以染成黑色或白色,任意两个相邻节点不能都是黑色,求方案数,结果对 取模。
样例输入
3
1 2
2 3
样例输出
5
树形DP:
我们设状态 为以 为根节点,且根节点颜色为( , )的子树中染色的方案数,那么可得状态转移方程为:
当 节点为白色时:
为黑色时:
状态初始化:
显然,当 节点为根节点时,
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 7;
const int MOD = 1e9 + 7;
vector<int> tree[MAXN];
long long dp[MAXN][2];
int n;
int x,y;
void dfs(int pos,int fa){
int cnt = 0;
for(int to : tree[pos]){
if(to != fa){
cnt++;
dfs(to,pos);
dp[pos][1] = (dp[pos][1] * dp[to][0]) % MOD;
dp[pos][0] = (dp[pos][0] * (dp[to][1] + dp[to][0]) % MOD) % MOD;
}
}
if(cnt == 0){
dp[pos][0] = dp[pos][1] = 1;
}
}
int main(){
scanf("%d", &n);
for(int i = 1;i <= n;i++){
dp[i][0] = dp[i][1] = 1;
}
for(int i = 1;i <= n - 1;i++){
scanf("%d%d", &x, &y);
tree[x].push_back(y);
tree[y].push_back(x);
}
dfs(1,0);
cout<<(dp[1][0] + dp[1][1]) % MOD;
return 0;
}