首页 > 小红树上染色
开通博客写题解
头像 AliLexiWalker
发表于 2026-04-16 02:17:48
树形DP分两种状态，当前点不染红则孩子必须染红，当前点染红则孩子可红可白，最后把根节点两种状态相加取模即可。 void solve(){ int n;cin>>n; vvi c(n+1); for(int i=1;i<n;++i){ int 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 pandaC222
发表于 2026-04-16 01:06:16
这是一道树形dp哦我们可以知道，如果一个节点为白色，那他的父节点一定得是红色，如果一个节点是红色，那他的父节点可以是白色或者红色这可以推出状态转移方程了，我们从根部向上转移：（0代表白色，1代表红色）dp[u][0] = (dp[u][0] * dp[v][1]) % mod; 父节点为白色子节点只 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 小男娘
发表于 2026-04-16 01:16:04
考虑一个点染不同颜色的条件喵如果这个点是红色，那么她的儿子红白都可以喵如果这个点是白色，那么她的儿子只能是红色喵所以只要记录每个子树根节点是红色和白色的方案数，就可以用乘法原理递推喵于是我们用树形 DP 轻松解决了这题喵，答案就是根的红白方案数之和喵 #include <iostream> 展开全文
去ta的博客 赞 (1) 回复(1) 收起
头像 Hauauah
发表于 2026-04-16 16:36:14
#include <iostream> #include <vector> using namespace std; #define int long long const int mod = 1e9 + 7; vector<vector<int>> 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 YouYeah
发表于 2026-04-16 19:54:23
#include<iostream> #include<vector> using namespace std; const int mod(1e9 + 7); vector<vector<int>> rec; pair<long long in 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 此在Dasein
发表于 2026-04-16 02:30:21
问题分析 该问题的核心约束是“不存在两个白色节点相邻”。在图论语境下，如果我们定义被染红的节点集合为 ，那么未被染红的节点（白色节点）集合为 。题目要求 中任意两个节点之间没有边相连，这等价于说 是一个独立集（Independent Set）。 进一步转化，若 是独立集，那么其补集 （即红色节 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 chenlan114
发表于 2026-04-16 12:10:47
栈优化的树形dp #include<bits/stdc++.h> using namespace std; using ll=long long; const ll N=1e5+5,mod=1e9+7; vector<vector<ll>>adj(N); vec 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 少女SKIKO
发表于 2026-04-21 11:25:17
dfs+线性dp从1开始做dfs，初始化dp[i][0],dp[i][1]为1dp[i][0]表示i节点,不染色的方案数观察得到dp方程如下：dp[i][1] =dp[i][1]*((dp[j][1]%mod+dp[j][0]%mod)%mod)%mod; dp[i][0] = (dp 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”