建设部网站资质,南充网站开发,组建个人网站,绥芬河市建设局网站链接#xff1a; 文章目录题目描述题意#xff1a;题解#xff1a;核心代码#xff1a;时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒
空间限制#xff1a;C/C 131072K#xff0c;其他语言262144K
64bit IO Format: %lld题目描述
牛牛最近得到了一颗树#xff0…链接 文章目录题目描述题意题解核心代码时间限制C/C 1秒其他语言2秒
空间限制C/C 131072K其他语言262144K
64bit IO Format: %lld题目描述
牛牛最近得到了一颗树根是 1 号节点他想要把这颗树染色。 每个节点可以染成白色和黑色牛牛认为一种染色方案是好的当且仅当任意两个黑点的 lca最近公共祖先的颜色也是黑色的。 求一共有多少种好的染色的方案。
输入描述: 第一行一个整数 n表示这棵树有 n个节点。 接下来 n-1行每行两个整数 u,v 表示 u,v之间有一条边。 输出描述: 一行一个整数表示所有合法的点的集合数量。 示例1 输入
4
1 2
2 3
2 4输出
14说明
共计14个集合满足题意。 注意空集也算进答案里面 示例2 输入
6
1 2
1 3
1 4
2 5
5 6输出
42备注: 1≤n≤10 6 ,1≤u,v≤n
题意
一个有n个节点的树其中根节点是1每个节点可以染色为黑与白如果有两个节点都是黑他们的最近公共祖先也必须是黑问有多少种涂色方案
题解
树形dp问题 我们可以用dp[x][0/1]来表示树上的节点x已经被染成黑色或者是白色的方案数黑用1白用0 因为题目只对黑色有限制条件所以如果x为黑色x的子节点可以是黑色也可以是白色但是如果x为白色x的子节点只能是白色或者是一个黑色因为如果有两个黑色x作为他俩的最近公共祖先也必须是黑色。 我们在处理时仅考虑染成黑色就行因为黑色除外的都要染成白色。1是染成黑色0为白色也可以理解成不处理 我们根据上述分析可以列出式子 dp [x ] [ 0 ] d p [ x] [ 0 ] d p[ y ] [ 1 ] d p [ y ][ 0 ] - 1 x点不染色的情况是x的子节点只能是白色或者是一个黑色因为存在空集所以减一 dp [x ] [ 1 ] dp[ x] [ 1 ] * dp [y ] [1 ] dp[ x] [ 1 ] * d p[ y ] [ 0 ] x染为黑x的子节点可以是黑色也可以是白色种类数量相乘 最后推到根节点1 答案就是dp[1][1]dp[1][0]
核心代码 void dpp(int x,int fa){dp[x][0]1dp[x][1]1;//先对当前节点初始化 int y; for(int ihead[x];~i;iedge[i].next){yedge[i].y;if(yfa)continue;//如果找到本身则跳过 dfs(y,x);//顺着树继续向下找 dp[x][0](dp[x][0]dp[y][1]dp[y][0]-1)%mod;dp[x][1]dp[x][1]*(dp[y][1]dp[y][0])%mod;}
}printf(%d,(dp[1][0]dp[1][1])%mod);每日一题倒是出现了好几个树形dp的题
