【树形DP】AT_dp_p Independent Set 题解

step 1 题意理解

• 有一棵有 $N$ 个顶点的树，编号为 $1,2,\dots ,N$。

• Taro 决定将每个顶点涂成白色或黑色。 在这里，不允许将相邻的两个顶点都涂成黑色。

• 找出可以涂色的方式数量，对 $10^9+7$ 取模。

step 2 样例解释

【样例输入】

3
1 2
2 3

【样例输出】

5

【样例解释】

step 3 做法解释

1. 考虑与没有上司的舞会相同的分类方法，对 $dp$ 数组额外开一维来记录上一层的是否是黑色
2. 对于每一次转移，都有以下转移方程：

• $$\{\begin{array}{ll}{f}_{i,j}=f_{i,j}\times (f_{v,0}+f_{v,1})& j=0\\ f_{i,j}=f_{i,j}\times f_{v,0}& j=1\end{array}$$
• $v$ 是 $i$ 的儿子

step 4 AC code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;

ll n,vis[100005],dp[100005][2];
vector<ll> tree[100005];

void dfs(int xx){
	dp[xx][0] = dp[xx][1] = 1;
	//cout << tree[xx].size();
	//cout << xx << endl;
	for(int zz : tree[xx]){
		if(!vis[zz]){
			vis[zz] = 1;
			dfs(zz);
			dp[xx][0] *= dp[zz][0] + dp[zz][1];
			dp[xx][0] %= mod;
			dp[xx][1] *= dp[zz][0];
			dp[xx][1] %= mod;
		}
	}
}

int main(){
	cin >> n;
	for(int i = 1; i < n ;i++){
		int x,y;
		cin >> x >> y;
		tree[y] . push_back(x);
		tree[x] . push_back(y);
	}
	vis[1] = 1;
	dfs(1);
	cout << (dp[1][0] + dp[1][1]) % mod;
	return 0;
}