w wyl123ly 的博客
MD

Independent Set

1 KB 2026.10.11 原文件

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;
}