Codeforces 461B 从开放连通块到树形计数 DP

ALGORITHM NOTES阅读地图

9个主要章节

1段代码示例

6组图片与图表

先明确状态与不变量，再对照手算、证明、边界和实现。

章节速览9 节 · 展开选择

树上差分把已有路径的贡献汇总到边，换根DP把一个方向的信息传给另一个方向。这次的问题不同：我们要决定哪些边保留、哪些边切断，并统计所有合法的决定。每个最终连通块都必须恰好含一个黑点。

关键不是“子树里一共有几个黑点”，而是：子树中哪些块已经封闭并满足条件，哪一个块还能够通过父边继续扩展？ 把这一边界说清，两个状态就足够，而且可以避免除法、前后缀积和递归栈。

先定义边界只有含子树根的块尚未封闭

其他块与父亲没有通道，必须已经各含一个黑点；开放块只允许零个或一个黑点。

再合并选择切边与留边分别检查合法性

用明确的边集合建立计数对应，避免凭感觉把几个乘积凑成公式。

官方题意、输入顺序与计数对象

461B · Appleman and Tree官方难度为 2000，标签为 dfs and similar、dp、trees，核对于2026-11-07。原题给一棵树，部分顶点为黑色，且保证至少一个黑点；选择一个边集合删除，使每个连通块恰有一个黑点，求这样的边集合数量，结果模1000000007。

官方范围为2≤n≤100000，点编号为0至n−1。输入第二行的pᵢ连接点i+1与pᵢ，且0≤pᵢ≤i。换成代码中“点v的父亲”表示，就是parent[v]<v。这不是一般树输入都具备的性质，后面的逆编号处理正是利用了这一条保证。

计数对象是删除的边集合，不是切边操作的先后顺序，也不是给每个块挑一个代表点。若总共有b个黑点，合法结果有b个连通块；树切掉k条边形成k+1块，因此合法集合一定恰好切b−1条边。但只固定切边数量还不够，仍可能出现一个块有两个黑点、另一个块没有黑点。

为什么必须区分开放块与封闭块

把0视为根。考虑某个点v的整棵子树：其中只有包含v的那一块，可能通过v与父亲的边继续连接外部。其余块一旦与v分离，以后就再也不能获得新的黑点，因此必须已经合法。

定义F₀(v)：v子树内部的切边方案中，所有不含v的封闭块都恰有一个黑点，包含v的开放块有零个黑点。定义F₁(v)：条件相同，但开放块有一个黑点。两个状态里的“零”或“一”，只描述开放块，不是整棵子树的黑点总数。

状态D1｜子树边界上保留的信息

F₀(v)：已封闭块全部合法，开放块含0个黑点
F₁(v)：已封闭块全部合法，开放块含1个黑点

状态值为切边方案数，无物理单位。开放块必须包含v；两个状态中的封闭块均已满足“恰好一个黑点”，不能等到父层再修复。公式与证明由本文独立推导。

开放块: 当前还含有子树根v的连通块。它可以经过父边继续扩展，也可能在父层切边时封闭。
封闭块: 已与v分离、不会再接到子树外部的块。它必须已经含一个黑点，不能留一个空块等待以后补点。
a₀、a₁与b₀、b₁: 分别表示父侧已合并部分的两个计数，以及本次子树的两个计数；转移同时使用旧父状态。

为什么没有F₂？若开放块已经有两个黑点，后来只能把它整体接到父块，或切掉父边让它封闭，都不能使它合法。至于在这个块内部再切一条旧边，那属于先前子问题应枚举的另一个方案，已经由其他状态路径表示，不是在未来凭空修复当前方案。

尚未合并孩子时，白点初始化为(1,0)，黑点初始化为(0,1)。这里的1表示“还没决定任何子边”的唯一空决策，不表示当前有一个合法的最终连通块。白点的开放块暂时没有黑点，仍可从孩子或父亲方向获得一个。

合并一个孩子，只看这条边切不切

设父侧旧状态为(a₀,a₁)，孩子u的完整子树状态为(b₀,b₁)。孩子子树中已经封闭的块不再改变，我们只需决定v—u这条边，并检查两个开放块的关系。

父侧开放块黑点数	孩子开放块黑点数	保留v—u	切断v—u
0	0	合为0，可继续扩展	孩子形成无黑点的封闭块，禁止
0	1	合为1	孩子封闭合法，父侧仍为0
1	0	合为1	孩子形成无黑点的封闭块，禁止
1	1	合为2，禁止	孩子封闭合法，父侧仍为1

把表中合法选择归类，父侧新状态为0的两种来源是“0与0保留”和“0与1切断”。新状态为1的三种来源是“1与0保留”“1与1切断”“0与1保留”。

转移D2｜无除法的两状态合并

new₀ = a₀(b₀+b₁)
new₁ = a₁(b₀+b₁) + a₀b₁

所有运算对M=1000000007取模。右侧a₀、a₁均为本次合并前的旧值，不能先写回new₀再拿它计算new₁。乘法对应不同子树中独立的边选择，加法对应互斥的状态/切边情形。

保留子边要求两边开放块黑点数之和不超过1；切断子边要求孩子开放块恰含1个黑点，父侧状态保持不变 — 图1｜原创合并规则图。每次只处理一条父子边；“允许暂时为0”只适用于仍开放的父块。查看原图

这个写法不需要计算某个乘积后再除以孩子贡献。模数是素数，并不意味着每个中间计数都有逆元：一个非零整数方案数也可能恰好对M余0。直接按互斥情形相加，既贴合证明，也避开了除零与模逆前提。

自检1：孩子的开放块没有黑点，能否切掉父子边，等其他孩子以后补上？

不能。父子边被切断后，该孩子开放块立即封闭，与其他孩子已经没有通道。其他孩子只能影响父侧的开放块，无法再给这个封闭块补黑点。

为什么不会漏算，也不会把同一集合算两次

对子树大小归纳。叶子的初始化显然对应唯一的内部空边集合。假定每个孩子的F₀、F₁都准确记录了对应方案，且不同方案对应不同内部切边集合。

合并孩子时，一个完整方案唯一决定：父侧此前的内部切边集合、孩子内部切边集合，以及连接边是否被切断。把任意合法方案限制回这三个部分，就会落入表中的唯一一行和唯一一种操作，因此不会漏掉，也不会同时归入两个相加项。

反过来，表中每个允许的组合都使所有新封闭块合法，而且留下的父侧开放块仍只有零个或一个黑点。不同组合至少在某条已处理边的状态上不同，所以乘法与加法得到的方案互不重复。重复这一过程，即得到v的完整状态。

根没有父亲，根的开放块最终也必须封闭。因此答案是F₁(0)，不能输出F₀(0)+F₁(0)。后者把“其他块都合法、唯独含根块没有黑点”的半成品也算进去了。

  flowchart TD
 A[孩子子树的封闭块已全部合法] --> B{连接父亲的边如何处理}
 B -->|保留| C[两个开放块合并]
 C --> D[黑点总数只能为零或一]
 B -->|切断| E[孩子开放块立即封闭]
 E --> F[孩子必须恰有一个黑点]
 D --> G[累计父侧新状态]
 F --> G

五个点，手算出五个边集合

取边0—1、0—2、1—3、1—4；黑点为2、3、4，白点为0、1。三个黑色叶子均为(0,1)。点1从白点初值(1,0)开始，依次合并3、4后得到(1,1)、(1,2)。

根0先合并孩子1：从(1,0)得到(3,2)；再合并黑色孩子2，得到(3,5)。最终只取第二项，答案为5。

处理位置	合并前父侧	孩子状态	合并后父侧
点1合并3	(1,0)	(0,1)	(1,1)
点1合并4	(1,1)	(0,1)	(1,2)
点0合并1	(1,0)	(1,2)	(3,2)
点0合并2	(3,2)	(0,1)	(3,5)

白色根0连接白色点1和黑色点2，点1连接黑色点3和4；点1状态为1和2，根完整状态为3和5，答案5 — 图2｜原创手算树。括号标注(F₀,F₁)，不是子树白点数与黑点数；根的F₀=3仍是未完成方案。查看原图

还可以不用DP核对这个例子：三黑点意味着必须切两条边，四条边中选两条共有6种。只有同时切0—1与0—2时，点1、3、4仍连在一起含两个黑点，且根0单独没有黑点，所以不合法。其余5种均满足条件。

官方第一个样例则只有白色根和两个黑色叶子，答案为2：根必须保留通往某一个黑叶的边，切掉另一条。它与五点例子的根状态含义一致，但不要把五点手算冒充官方样例。

用输入编号替代递归后序

原题保证parent[v]<v。沿父亲方向编号严格减小，因此任何后代编号都大于祖先。在n−1、n−2、…、1的顺序中，一个点被合并给父亲时，它的所有孩子已经先合并完成；这正是需要的自底向上顺序。

我们可以先给所有点按颜色初始化，再逆编号把点v的完整状态合并进parent[v]。每条边只处理一次，不必建立邻接表，也不必递归。若把代码迁移到任意编号的边表输入，应先通过非递归遍历生成父子顺序，再反向处理；不能继续假设逆编号就是后序。

#include <iostream>
#include <vector>
using namespace std;

constexpr long long MOD = 1000000007LL;

long long count_partitions(const vector<int>& parent,
                           const vector<int>& black) {
    const int n = static_cast<int>(parent.size());
    vector<long long> zero(n), one(n);
    for (int v = 0; v < n; ++v) {
        zero[v] = (black[v] == 0);
        one[v] = (black[v] == 1);
    }
    for (int v = n - 1; v >= 1; --v) {
        const int p = parent[v];
        const long long a0 = zero[p], a1 = one[p];
        const long long b0 = zero[v], b1 = one[v];
        const long long sum = (b0 + b1) % MOD;
        zero[p] = a0 * sum % MOD;
        one[p] = (a1 * sum + a0 * b1) % MOD;
    }
    return one[0];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<int> parent(n, -1), black(n);
    for (int v = 1; v < n; ++v) cin >> parent[v];
    for (int& color : black) cin >> color;
    cout << count_partitions(parent, black) << '\n';
}

边界与实现中最容易混淆的地方

仅一个黑点时，所有边都必须保留；否则切出的某块必定没有黑点，所以答案为1。所有点都黑时，所有边都必须切，答案也为1。白色中心接k个黑色叶子的星形树，根必须选择且只选择一个黑叶保留，因此答案为k；再接若干白色叶子，它们的边被迫保留，不改变这个计数。

链上若黑点依次出现在q₁、q₂、…、q_b，每两个相邻黑点之间必须恰好切一条边，选择数为各段距离的乘积；两端的白点区间不能切。这个独立特例既能帮助理解，也能核对十万点长链的模数结果。

官方不包含全白树。作为状态定义的额外检查，全白树应得到根F₁=0；这不能被写成官方允许的输入。树有十万点时，递归可能受到运行环境栈空间限制，而逆编号循环没有这一风险。合并状态必须保存a₀、a₁旧值，写回顺序不应该改变数学公式。

自检2：根的两个状态都满足“已封闭块合法”，为什么不能相加？

根的开放块也属于最终结果，已经没有父边可继续扩展。F₀表示含根块没有黑点，不能封闭；只有F₁满足最终条件。

自检3：父侧和孩子各有一个黑点，是否所有组合都应丢弃？

只禁止保留这条连接边。切断时，孩子开放块以一个黑点合法封闭，父侧仍有一个黑点，因此a₁b₁是new₁中的合法贡献。

自检4：换成任意编号的无向边表，还能直接从n−1循环到1吗？

不能。逆编号可行的依据是官方parent[v]<v。任意编号不保证孩子先处理，需要先生成父子关系与遍历顺序，再逆序做相同合并。

  flowchart LR
 A[所有点按颜色初始化] --> B[按官方父编号性质逆序处理]
 B --> C[取孩子完整状态与父侧旧状态]
 C --> D[用切边留边的互斥情形合并]
 D --> E[根只取开放块含一个黑点的状态]

怎样独立验证这两个状态

小树参考可以直接枚举所有删除边集合，再用独立连通分量检查每块黑点数是否为1。这条参考路径不使用开放块DP，可以发现“切出空块”“两个黑点仍连接”“根状态相加”等转移错误。

再把同一棵带颜色的树换根、按新的父子顺序重新编号，答案应不变。因为题目计数的是原无向树的边集合，根只是算法的组织方式，不应改变问题本身。大树则用单黑点、全黑点、链距离乘积与星形封闭式核对，实际运行完整程序，而不是仅编译一个未调用的函数。

参考资料与衔接

Codeforces：461B，Appleman and Tree。官方题目提供输入保证、模数、样例、2000难度和三个官方标签。本篇状态、证明、五点例子与程序独立组织。返回状态D1。
本站树结构路线。树上DFS与子树汇总训练父子方向，换根DP讨论方向消息。本题只需固定根的计数，不需要为所有根计算不同答案。
本站边界与证明笔记。反例与适用条件用于复核“逆编号处理”依赖的输入性质；代码契约列出当前程序的适用范围。站内衔接不是竞赛元信息的替代来源。