牛客练习赛62 C.牛牛染颜色

题意：牛牛最近得到了一颗树，根是 1 号节点，他想要把这颗树染色。
每个节点可以染成白色和黑色，牛牛认为一种染色方案是好的当且仅当任意两个黑点的 lca（最近公共祖先）的颜色也是黑色的。
求一共有多少种好的染色的方案。答案 mod(1e9+7).
分析：

• 树形dp.考虑当前节点为根节点的子树方案数，dp[u][0]为选择当前点进入集合的方案,dp[u][1]为不选择当前点进入集合的方案.
• 那么考虑转移.对于当前节点dp[u][0]方案，当前节点为黑色的方案，那么子节点方案都合法.转移方程：

对于dp[u][1]方案数,当前节点为白色，那么子节点不能同时选，那么转移方程：

减一是因为子节点方案中的空集计算重复.

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int mod=1e9+7;
const int maxn=1e6+10;
int head[maxn],nxt[maxn<<1],to[maxn<<1],cnt;
int n;
ll dp[maxn][2];

int read()
{
    int x=0;char s=getchar();
    for( ;isdigit(s);x=x*10+s-48,s=getchar());
    return x;
}

void add( int u,int v )
{
    to[++cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
}

void init()
{
    memset(head,-1,sizeof(head));
    cnt=0; 
}

int qpow( int x,int y )
{
    int ans=1;
    while( y ) 
    {
        if( y&1 ) ans=ans*x%mod;
        y>>=1;
        x=x*x%mod;
    }
    return ans;
}

void dfs( int u,int fa )
{
    ll a=1,b=1;
    for( int i=head[u];~i;i=nxt[i] )
    {
        int v=to[i];
        if( v==fa ) continue;
        dfs(v,u);
        a=(a+dp[v][0]+dp[v][1]+mod-1)%mod;
        b=b*(dp[v][0]+dp[v][1])%mod;
    }
    dp[u][1]=a;
    dp[u][0]=b;
}

int main()
{
    n=read();
    init();
    for( int i=1,u,v;i<n;i++ )
    {
        u=read(),v=read();
        add(u,v);add(v,u); 
    }
    dfs(1,0);
    ll ans=(dp[1][0]+dp[1][1])%mod;
    printf("%lld\n",ans);
    return 0;
}