首页 > 牛牛染颜色
开通博客写题解
头像 Kur1su
发表于 2020-04-26 21:14:38
Solution 考虑树形dp, 表示以 为根的子树至少含有一个黑节点的方案数(全白的后面+1即可)那么考虑两种情况 染为黑色, 则子节点为什么颜色都无所谓, ( 为子节点), 其中1表示子结点的子树全为1 染为白色, 则子节点必须只有一个黑, ( 为子节点) 那么最后答案就是 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 Lskkkno1
发表于 2020-04-24 22:14:09
牛牛染颜色 题目描述 把树上一些染成黑色，满足任意两个黑色点的 lca 也被染成黑色了。 求染色方案数对 取模。 正解 考虑 dfs 的过程中： 一个点的两个不同的子树内有节点被染色，这个节点就必须被染色。 否则这个点它可以任意选择染色或者不染色。 那么很容易设出状态 表示一个点的子树 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 pdd内推哈哈哈
发表于 2020-04-25 02:13:03
给定一棵树，求有多少个集合,满足 树形,设表示选择节点的方法数，表示不选择节点的方法数。 对于 ,显然有 。对于 ,首先可以选择空集也就是 , 然后不同子树不能同时选择而且每颗子树都会有空的情况，所以还要减去每颗子树空的情况。 #include<bits/stdc++.h> 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 18duangduang
发表于 2020-04-25 12:30:56
题意：牛牛最近得到了一颗树，根是 1 号节点，他想要把这颗树染色。每个节点可以染成白色和黑色，牛牛认为一种染色方案是好的当且仅当任意两个黑点的 lca（最近公共祖先）的颜色也是黑色的。求一共有多少种好的染色的方案。答案 mod(1e9+7).分析： 树形dp.考虑当前节点为根节点的子树方案数，dp 展开全文
去ta的博客 赞 (0) 回复(1) 收起
头像 19_hanhan
发表于 2020-04-26 22:33:50
题目 题目描述 ： 牛牛最近得到了一颗树，根是 1 号节点，他想要把这颗树染色。  每个节点可以染成白色和黑色，牛牛认为一种染色方案是好的当且仅当任意两个黑点的 lca（最近公共祖先）的颜色也是黑色的。  求一共有多少种好的染色的方案。  答案可能很大，请输出答案 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 回归梦想
发表于 2020-05-05 18:28:17
链接： @[toc] 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 131072K，其他语言262144K 64bit IO Format: %lld 题目描述 牛牛最近得到了一颗树，根是 1 号节点，他想要把这颗树染色。每个节点可以染成白色和黑色，牛牛认为一种染色方案是好的当且仅 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”