【题解】数字积木：树上 MEX 求和与动态骨架维护 (DFS版)
1. 题目背景与大意
题目名称： Bingbong的积木树 (Tree MEX Sum)
给定一棵包含n 个节点的树，节点权值为0 \sim n-1 的全排列。
定义一个 连通子图 的权值为：该子图所有节点权值中 未出现过的最小非负整数（即\text{MEX}）。
求树上 所有 连通子图的权值之和。答案对10^9 + 7 取模。
数据范围：N \le 2 \times 10^5。
2. 涉及算法与核心思想
这道题是一道综合性很强的树上计数问题，解题过程中涉及以下核心算法与思想：
贡献法 (Contribution Technique)：
将“求每个子图的 MEX 值之和”转化为“求每一个数值k 对答案的贡献次数”。
树形 DP (Tree DP)：
预处理以每个节点为根的子树中，包含根节点的连通子图方案数。
斯坦纳树 (Steiner Tree) / 最小连通骨架：
动态维护包含特定点集\{0, 1, \dots, k\} 的最小连通子图。
裂项相消与动态维护：
利用乘法逆元，通过“除旧乘新”的操作，在O(1) 或O(\text{dist}) 时间内更新骨架的方案数。
模运算下的除法处理：
使用自定义结构体处理模数为0 时没有逆元的情况（工程技巧）。
3. 核心解题步骤详解
步骤一：视角的转换（积分思想）
直接枚举所有连通子图并计算\text{MEX} 是不可行的。我们需要利用数学转化：
通俗解释：
我们将总分拆解为层级分。
如果一个子图包含了\{0\}，它至少贡献1 分。
如果它还包含了\{1\}（即拥有\{0, 1\}），它再贡献1 分。
以此类推，对于每一个k，我们只需要计算：树上有多少个连通子图同时包含了节点0 到k-1。
步骤二：预处理子树方案 (DFS)
我们需要知道每个节点作为“挂件”时的方案数。
定义DP[u]：在以u 为根的子树中，必须包含u 的连通子图方案数。
转移方程：
DP[u] = \prod_{v \in son(u)} (DP[v] + 1)这里的+1 代表子节点v 这个分支可以选择“不选”。
实现：跑一遍 DFS 即可求出所有DP 值和父子关系。
步骤三：动态维护“骨架”
我们从k=1 开始，依次加入节点1, 2, \dots, n-1。
为了连通\{0, \dots, k\}，这些点在树上的最小连通路径构成了 “骨架”。
当我们要把一个新节点u 加入骨架时，需要将其到当前骨架的路径全部“点亮”。对于路径上的每个点，发生如下状态转变：
状态转变：该节点从 “可选的挂件” 变成了 “必选的骨架”。
数学操作：
剔除旧贡献：作为挂件时，它贡献了\times (DP[u] + 1)。现在它不再“可选”，所以要 除以(DP[u] + 1)。
加入新贡献：变成骨架后，它的所有子节点变成了新的挂件。我们需要把它们的贡献\times (DP[v] + 1) 乘入 总方案数。
这一步利用了 Safe_Product 结构体来安全地进行模运算除法。
4. 关键工程细节：Safe_Product
在实现“除法”时，有一个巨大的坑：模数0 问题。
在模10^9+7 下，如果(DP[u] + 1) 恰好是模数的倍数，通过费马小定理求逆元会失效（$0$ 没有逆元）。
我们必须封装一个结构体来通过 “记账法” 处理0：
单独记录因子中0 的个数 (
zero_cnt)。乘0 时计数器+1，除0 时计数器-1。
只有计数器为0 时才输出
product，否则输出0。
5. AC 代码 (C++ DFS版)
C++
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using i64 = long long;
const int mod = 1e9 + 7;
// --- 基础工具：快速幂求逆元 ---
int power(int a, int k) {
int res = 1;
while (k) {
if (k & 1) {
res = 1ll * res * a % mod;
}
a = 1ll * a * a % mod;
k >>= 1;
}
return res;
}
// --- 核心工具：Safe_Product ---
// 用于处理模运算中“除以 0”的特殊情况
struct Safe_Product {
int zero_cnt = 0;
int product = 1;
// 安全乘法
void mul(int x) {
x %= mod; // 【关键】必须先取模，防止 x 是 mod 的倍数
if (x == 0) {
zero_cnt++;
} else {
product = 1ll * product * x % mod;
}
}
// 安全除法 (乘逆元)
void div(int x) {
x %= mod; // 【关键】必须先取模
if (x == 0) {
zero_cnt--;
} else {
product = 1ll * product * power(x, mod - 2) % mod;
}
}
// 获取真实值
int val() {
if (zero_cnt > 0) {
return 0;
} else {
return product;
}
}
};
void solve() {
int n;
cin >> n;
vector<int> a(n), pos(n);
// 读入权值，pos[v] 记录权值为 v 的节点编号
for (int i = 0; i < n; i ++ ) {
cin >> a[i];
pos[a[i]] = i;
}
vector<vector<int>> adj(n);
for (int i = 1; i < n; i ++ ) {
int u, v;
cin >> u >> v;
u -- , v -- ; // 转为 0-based 索引
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<int> fa(n);
vector<Safe_Product> dp(n);
// --- 步骤一：DFS 预处理 ---
// 计算父子关系 fa[] 和子树方案数 dp[]
auto dfs = [&](auto && self, int u, int p) -> void {
fa[u] = p;
for (auto v : adj[u]) {
if (v != p) {
self(self, v, u);
// 状态转移：累乘 (子树方案 + 1)
dp[u].mul(dp[v].val() + 1);
}
}
};
int root = pos[0]; // 必须包含 0，故以 0 所在节点为根
dfs(dfs, root, -1);
vector<int> st(n); // st[u]=1 表示 u 已经在骨架中
st[root] = 1;
auto sum = dp[root]; // 当前骨架的总方案数
int ans = sum.val(); // k=1 时的贡献 (即包含 {0} 的方案数)
// --- 步骤二：动态维护骨架 ---
// 依次尝试加入 1, 2, ..., n-1
for (int i = 1; i < n; i ++ ) {
int u = pos[i];
// 从 u 向上爬，直到遇到已经点亮的骨架
while (!st[u]) {
st[u] = 1;
// 核心逻辑：
// 1. u 从“挂件”变为“骨架”，除掉旧贡献 (DP[u]+1)
sum.div(dp[u].val() + 1);
// 2. u 的子节点变为新的“挂件”，乘上新贡献
// 注意：只乘子节点，不要把父节点乘进去了
for (auto v : adj[u]) {
if (v != fa[u]) {
sum.mul(dp[v].val() + 1);
}
}
u = fa[u];
}
// 累加当前 MEX >= i+1 的方案数
ans = (ans + sum.val()) % mod;
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
// cin >> T;
while (T -- ) {
solve();
}
return 0;
}
6. 复杂度分析
时间复杂度：
预处理 DFS：每个节点访问一次，复杂度为O(N)。
动态维护：虽然代码中有双重循环，但均摊分析如下：
骨架扩展：每个节点最多只会被加入骨架一次（通过
st数组标记），这部分均摊是O(N)。乘法逆元：每次加入骨架时，涉及到除法运算。求逆元的时间复杂度是O(\log M)（其中M = 10^9+7）。
总时间复杂度：整体为O(N \log M)。
空间复杂度：
需要存储邻接表、
DP数组、父节点数组fa等，均为线性空间，故空间复杂度为O(N)。
评论