---
title: Independent Set
type: 题解
tags:
  - 信息竞赛题解
  - 树形DP
---

# **Independent Set**

给一棵树，每一个点可以染成黑色或白色，任意两个相邻节点不能都是黑色，求方案数，结果对 $10^9+7$ 取模。

### 样例输入 

```
3
1 2
2 3
```

### 样例输出 

```
5
```

树形DP:

我们设状态 $dp_{i,0/1}$ 为以 $i$ 为根节点，且根节点颜色为（ $1 - 黑色$，$0 - 白色$ ）的子树中染色的方案数，那么可得状态转移方程为：

当 $i$ 节点为白色时：

$ dp_{i,0} = \prod (dp_{to_i,0} + dp_{to_i,1}) $

为黑色时：

$dp_{i,1} = \prod dp_{to_i,0}$

状态初始化：

显然，当 $i$ 节点为根节点时，$ dp_{i,0} = dp_{i,1} = 1$

```cpp
#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;
}
```

$done$
