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

传送门：牛客 - 练习赛62C

思路分析

设$dp[u][0/1]$表示选不选这个节点的方案数
显然 $dp[u][1]=\prod_{v==son_u}(dp[v][0]+dp[v][1])$
如果u不选的话，那么只能有一个子树能选节点
每棵子树都有空集的情况，所以减去重复的空集部分
显然 $dp[u][0]=1+\sum_{v==son_u}(dp[v][1]+dp[v][0]-1)$

样例输入

4
1 2
2 3
2 4

样例输出

14

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <chrono>
#include <random>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) (x).size()
#define lowbit(x) (x)&(-x)
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 0x3f3f3f3f;
const int N=1e6+10;
const int mod=1e9+7;

ll dp[N][2];

struct node{
    int v,next;
}e[N*2];

int head[N*2],cnt;

void add(int u,int v){
    e[++cnt].v=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}

void dfs(int u,int fa){
    dp[u][1]=dp[u][0]=1;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].v;
        if(v==fa) continue;
        dfs(v,u);
        dp[u][0]=(dp[u][0]+dp[v][0]+dp[v][1]-1)%mod;
        dp[u][1]=(dp[u][1]*(dp[v][1]+dp[v][0]))%mod;
    }
}


int main() {
    IOS;
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    int n;
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    dfs(1,0);
    cout<<(dp[1][0]+dp[1][1])%mod<<endl;



    return 0;
}