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

原文地址：https://blog.csdn.net/dengqingrui123/article/details/142692602

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！