CF 461B Appleman and Tree

题目描述

https://codeforces.com/problemset/problem/461/B

Solution

注意到黑点有且仅有一个

所以我们令 $f[u]$ 表示 $u$ 的子树已经处理完毕，还剩一个全白的连通块，$g[u]$ 表示还剩一个仅有一个黑点的连通块

那么我们注意到如果 $u$ 为白点，那么 $f[v]$ 一定与 $u$ 相连，$g[v]$ 一定断开，$u$ 为黑点相反

通过简单讨论可以得到转移，具体可以参考代码

时间复杂度 $O(n\log n)$，实际书写时，可以优化掉 $\log$

#include <iostream>
#define maxn 100010
#define ll long long
using namespace std;

const int p = 1000000007;

ll pow_mod(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1, x = x * x % p)
        if (n & 1) s = s * x % p;
    return s;
} 

int n, c[maxn];

struct Edge {
    int to, next;
} e[maxn * 2]; int c1, head[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}

ll f[maxn], g[maxn];
void dfs(int u, int fa) {
    ll mul = 1; 
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa) continue;
        dfs(v, u); mul = mul * (f[v] + g[v]) % p; 
    }
    if (c[u] == 1) return f[u] = 0, g[u] = mul, void();
    f[u] = mul;
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa) continue;
        g[u] = (g[u] + mul * pow_mod(f[v] + g[v], p - 2) % p * g[v]) % p;
    } 
}

int main() { fill(head, head + maxn, -1);
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 2, x; i <= n; ++i) cin >> x, ++x, add_edge(x, i);
    for (int i = 1; i <= n; ++i) cin >> c[i];
    dfs(1, 0); cout << g[1] << "\n"; 
    return 0;
}