题目

题目描述 ：
牛牛最近得到了一颗树，根是 1 号节点，他想要把这颗树染色。 
每个节点可以染成白色和黑色，牛牛认为一种染色方案是好的当且仅当任意两个黑点的 lca（最近公共祖先）的颜色也是黑色的。 
求一共有多少种好的染色的方案。 
答案可能很大，请输出答案对1e9 + 7取模后的结果。

输入描述：
第一行一个整数 n，表示这棵树有 n 个节点。
接下来n − 1行，每行两个整数u，v表示u，v之间有一条边。

输出描述：
一行一个整数，表示所有合法的点的集合数量。

解析

简单理解题意：就是两个黑色节点最近的共同祖先，一定是黑色；或者说是一个节点的左子树和右子树都有黑色节点的话，这个节点一定是黑色的。

知道题目意思以后，我们不难发现这是一道dp的题目（我当然发现了！只是不会写而已），所以超菜的我不厌其烦的还是要说这句话：
  • 动态规划的基础就是递推！
那么我们就来推一下递推公式：
  1. 首先每个节点有两种情况：<1>节点为黑色（我们用dp[pos][0]表示）。<2>节点为白色（我们用dp[pos][1]表示）。
  2. 首先我们来讲黑色：黑色的节点，无论下面是什么情况（有没有黑色子节点都可以是黑的），
    所以我们就可以肆无忌惮的得到状态转移方程：（乘法表示关联）
  3. 然后我们来讲白色：白色的节点，要考虑下面是否有两棵子树都有黑色的情况，所以我们单独把每个子节点是（黑/白）的情况加起来就好了。
    所以状态转移方程就是：（加法表示独立存在）
  4. 然后记得过程取余就好了。

又到了传统异能：写代码：
  1. 首先用前向星保存好我们的边（前向星还不是很熟的看专栏，点这里）。
  2. 然后用dfs的方法，对整棵树的所有边进行遍历。并用上两个状态转移方程。
  3. 最后把根节点的两种颜色之和取模输出来就好了。

AC代码 

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
//代码预处理区

const int MOD = 1e9 + 7;
const int MAX = 1e6 + 7;
struct node {
    int v, next;//边的终点和同起点的下一条边
} edge[MAX << 1];
int head[MAX], total = 0;//前向星初始化变量
ll dp[MAX][2];//树状dp数组，第二个参数为0节点是黑色，1是白色。

//全局变量区

template<class T>inline void read(T& res);//整型快读函数
void add_edge(int u, int v);//前向星加边函数
void dfs(int x, int fa);//深度优先遍历，遍历树
//函数预定义区

int main() {
    int n; read(n);//总边数
    memset(head, -1, sizeof head);
    for (int i = 1; i < n; i++) {
        int u, v; read(u); read(v);
        add_edge(u, v); add_edge(v, u);
    }
    //前向星初始化
    dfs(1, 0);
    printf("%lld\n", (dp[1][0] + dp[1][1]) % MOD);
    return 0;
}
template<class T>inline void read(T& res) {
    char c; T flag = 1;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
            flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    res *= flag;
}
void add_edge(int u, int v) {
    edge[++total].v = v;
    edge[total].next = head[u];
    head[u] = total;
    //起始点为1的加边
}
void dfs(int u, int fa) {
    ll zero = 1, one = 1;
    for (int i = head[u]; ~i; i = edge[i].next) {
        int v = edge[i].v;
        if (v != fa) {
            dfs(v, u);
            zero = zero * (dp[v][0] + dp[v][1]) % MOD;
            one = (one + dp[v][0] + dp[v][1] - 1 + MOD) % MOD;
            //黑色和白色的状态转移方程
        }
    }
    dp[u][0] = zero; dp[u][1] = one;
}
//函数区