黑白树分割

数据规模：$2 \le n \le 10^5$，$0 \le p_i \le i$，$x_i \in \{0,1\}$，且至少有一个 $x_i = 1$。

思路

状态定义。 删边方案可以自底向上决策：对每个节点 $u$，只关心「$u$ 所在的连通块」目前含几个黑点，因为这块以后要和父亲相连或被父亲切断。设

• $f(u,0)$：$u$ 的子树内所有边都已决定去留，子树内除 $u$ 所在块之外的连通块都恰好含一个黑点，且 $u$ 所在块含 $0$ 个黑点的方案数；
• $f(u,1)$：同上，但 $u$ 所在块恰好含 $1$ 个黑点。

把 $u$ 所在块的黑点数作为对外状态，正是因为它要和父亲那一侧合并；其余连通块已经封闭，无法再变化，所以只要它们合法就行。

初值只由 $u$ 自己的颜色决定：黑点时 $(f(u,0), f(u,1)) = (0,1)$，白点时 $(1,0)$。

合并儿子。 设 $u$ 已并入部分儿子的状态为 $(a_0, a_1)$，现在要并入儿子 $v$，其状态为 $(b_0, b_1)$。边 $(u,v)$ 只有两种处理：

• 删掉这条边：$v$ 所在块从此独立，必须已经恰好含一个黑点，因此只能贡献 $b_1$，并且 $u$ 这一块的黑点数不变；
• 保留这条边：两块合并成一个块，黑点数相加，结果不能超过 $1$，所以只允许 $0+0$、$1+0$、$0+1$ 三种组合。

逐项相加得到

$a_0' = a_0 b_1 + a_0 b_0, \qquad a_1' = a_1 b_1 + a_1 b_0 + a_0 b_1.$

其中 $a_0 b_1$ 在 $a_0'$ 与 $a_1'$ 里各出现一次：$u$ 块无黑点而 $v$ 块有一黑点时，切边（$v$ 块封闭，$u$ 块仍是零黑点）与留边（黑点由 $v$ 带入 $u$ 块）都合法，且这是两种不同的删边方案。$a_0 b_0$ 只能是留边（$u$ 块本身零黑点，无法接受一个零黑块的子块被封为独立连通块），$a_1 b_1$ 只能是切边（两块各有一黑点，合并后会有两个黑点）。

答案与边界。 根节点并入全部儿子后不再有父亲，它所在的块必须恰好含一个黑点，答案为 $f(\text{root}, 1)$。若取 $f(\text{root},0)$，根所在块会留下一个不含黑点的连通块，不合法；题目保证至少一个黑点，因此这些非法方案没有被别处「补救」的可能。

为什么不需要建图。 题面保证 $p_i \le i$，即节点 $i+1$ 的父亲编号严格小于 $i+1$，所以子节点编号总比祖先大。于是从 $n-1$ 倒序扫到 $1$，把每个节点已经合并完毕的状态并入父亲即可：扫描到 $u$ 时，$u$ 的所有儿子编号都大于 $u$，必然已经并入；同时也不会有节点被并入后又被修改。

复杂度

每个节点恰好被并入父亲一次，转移是常数次乘法与加法，时间 $O(n)$；只存父数组、颜色和两个 DP 数组，空间 $O(n)$。

仓颉实现

按倒序扫描节点，用两个长度为 $n$ 的数组存状态，父数组直接从第二行输入获得。

import std.env.*
import std.convert.*

main() {
    let MOD: Int64 = 1000000007
    let reader = getStdIn()
    let n = Int64.parse(reader.readln().getOrThrow())
    let par = Array<Int64>(n, { _ => 0 })
    let ps = reader.readln().getOrThrow().split(" ", removeEmpty: true).map({ p: String => Int64.parse(p) })
    for (i in 0..(n - 1)) {
        par[i + 1] = ps[i]
    }
    let x = reader.readln().getOrThrow().split(" ", removeEmpty: true).map({ p: String => Int64.parse(p) })
    let dp0 = Array<Int64>(n, { _ => 0 })
    let dp1 = Array<Int64>(n, { _ => 0 })
    for (i in 0..n) {
        if (x[i] == 1) {
            dp1[i] = 1
        } else {
            dp0[i] = 1
        }
    }
    var u = n - 1
    while (u >= 1) {
        let p = par[u]
        let a0 = dp0[p]
        let a1 = dp1[p]
        let b0 = dp0[u]
        let b1 = dp1[u]
        dp0[p] = (a0 * b1 + a0 * b0) % MOD
        dp1[p] = (a1 * ((b1 + b0) % MOD) + a0 * b1) % MOD
        u -= 1
    }
    println(dp1[0])
}