链接：

@[toc]

时间限制：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]=1；
    dp[x][1]=1;//先对当前节点初始化 
    int y; 
    for(int i=head[x];~i;i=edge[i].next)
    {
        y=edge[i].y;
        if(y==fa)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的题