【树形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;
}