题解 [牛客练习赛62 C] 牛牛染颜色

• 牛牛染颜色

题目描述

把树上一些染成黑色，满足任意两个黑色点的 lca 也被染成黑色了。

求染色方案数对 取模。

正解

考虑 dfs 的过程中：

1. 一个点的两个不同的子树内有节点被染色，这个节点就必须被染色。

2. 否则这个点它可以任意选择染色或者不染色。

那么很容易设出状态 表示一个点的子树内（包括自己）是否有节点染色的方案数。

根据上面两个描述很容易得到下面的转移方程：

1. 

2. 只有一颗子树内染了色的方案数（当前节点选 0） + （当前节点选 1）

时间复杂度 。

代码

#include <bits/stdc++.h>
#define N 1000005

using namespace std;

const int mod = 1e9 + 7;

int n;
int head[N], nex[N << 1], to[N << 1], ecnt;
int f[N][2];

inline void addE(int u, int v) {
    to[++ecnt] = v;
    nex[ecnt] = head[u], head[u] = ecnt;
}

inline int fpm(int x, int y) {
    int r = 1;
    while(y) {
        if(y & 1) r = 1LL * x * r % mod;
        x = 1LL * x * x % mod, y >>= 1;
    }
    return r;
}

void dfs(int u, int fa) {
    int r1 = 1, r2 = 1, r3 = 0;
    for(int i = head[u], v; i; i = nex[i]) {
        v = to[i];
        if(v == fa) continue;
        dfs(v, u);
        r1 = 1LL * r1 * (f[v][0] + f[v][1]) % mod;
        r2 = 1LL * r2 * f[v][0] % mod;
    }
    for(int i = head[u], v; i; i = nex[i]) {
        v = to[i];
        if(v == fa) continue;
        r3 = (r3 + 1LL * r2 * fpm(f[v][0], mod - 2) % mod * f[v][1]) % mod;
    }
    f[u][0] = r2;
    f[u][1] = (r1 + r3) % mod;
}

inline int read() {
    int x = 0; char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    return x;
}

int main() {
    n = read();
    for(int i = 1, u, v; i < n; ++i) {
        u = read(), v = read();
        addE(u, v), addE(v, u);
    }

    dfs(1, 0);

    int ans = (f[1][0] + f[1][1]) % mod;
    printf("%d\n", ans);
    return 0;
}