题解

题目大意

给定一棵 $n$ 个节点的树，有 $k$ 支救援队。每支救援队的救援范围是树的一个连通子集。我们需要计算有多少种救援范围的分配方案，使得存在至少一个节点 $u$，对于每支救援队，$u$ 都在其救援范围内，且救援范围内任意节点到 $u$ 的距离不超过 $L$。

问题分析

关键条件理解

对于节点 $u$ 和救援范围 $S$，条件 "$u$ 可被救援范围为 $S$ 的救援队到达" 等价于：

1. $u \in S$
2. $\forall v \in S, \text{dist}(u,v) \leq L$
3. $S$ 是连通子集

这意味着以 $u$ 为中心、半径为 $L$ 的连通块（即包含 $u$ 且所有节点到 $u$ 距离不超过 $L$ 的极大连通子集）必须是 $S$ 的子集。

问题转化

我们需要计算满足以下条件的方案数：存在节点 $u$，对于所有 $i \in [1,k]$，救援队 $s_i$ 的救援范围 $S_i$ 都包含以 $u$ 为中心、半径为 $L$ 的连通块。

算法思路

核心思想

使用容斥原理和树形DP来计数。

定义：

• $R(u)$：以 $u$ 为中心、半径为 $L$ 的连通块
• $R'(u)$：以 $u$ 为中心、半径为 $L-1$ 的连通块

对于固定的 $u$，所有救援队都覆盖 $R(u)$ 的方案数为：

$$\left(\prod_{i=1}^k \text{包含 } R(u) \text{ 的连通子集数}\right) = \left(\text{包含 } R(u) \text{ 的连通子集数}\right)^k $$

但是直接求和会重复计算，因此需要容斥。

容斥原理

设 $A_u$ 表示所有救援队都覆盖 $R(u)$ 的方案集合。

根据容斥原理：

$$\text{答案} = \sum_{u} |A_u| - \sum_{u \neq \text{root}} |A_u \cap A_{\text{parent}(u)}| + \cdots $$

实际上，代码中使用了更简洁的容斥：

$$\text{答案} = \sum_{u=1}^n f(u)^k - \sum_{u=2}^n g(u)^k $$

其中：

• $f(u)$：包含 $R(u)$ 的连通子集数
• $g(u)$：同时包含 $R(u)$ 和 $R'(\text{parent}(u))$ 的连通子集数

树形DP实现

1. 长链剖分

首先进行 DFS 计算每个节点的深度和重儿子（最长链），为后续DP优化空间。

2. 自底向上DP (gt_f)

计算 $f(u,d)$：在以 $u$ 为根的子树中，选择包含 $u$ 且最远节点距离 $u$ 不超过 $d$ 的连通子集数。

使用变换 $F(u)$ 来维护DP值，避免重复计算。

3. 自顶向下DP (gt_g)

计算 $g(u,d)$：考虑整棵树，选择包含 $u$ 且最远节点距离 $u$ 不超过 $d$ 的连通子集数。

结合自底向上和自顶向下的信息。

代码关键部分解析

数据结构

struct tag {
    int a, b;
    int gt(int x) { return ((ll)a * x + b) % p; }
    int inv(int x) { return (ll)(x - b + p) * pw(a, p - 2) % p; }
    tag ml(int x) { return {(int)((ll)a * x % p), (int)((ll)b * x % p)}; }
};

这个结构体维护线性变换 $x \to a \cdot x + b$，用于高效更新DP值。

主要变量

• r[u]: $f(u)$ - 包含 $R(u)$ 的连通子集数
• s[u]: 包含 $R'(u)$ 的连通子集数
• t[u]: 从上方看，包含 $u$ 且满足距离限制的连通子集数

最终计算

int ans = 0;
for (int u = 1; u <= n; ++u) {
    ans += pw((ll)(r[u] - 1 + p) % p * t[u] % p, k);
    // 所有救援队都覆盖 R(u) 的方案数
}
for (int u = 2; u <= n; ++u) {
    ans -= pw((ll)(s[u] - 1 + p) % p * (t[u] - 1 + p) % p % p, k);
    // 减去重复计算的部分
}

复杂度分析

• 时间复杂度: $O(nk)$，其中 $k$ 是救援队数量（最大为10）
• 空间复杂度: $O(n)$，使用长链剖分优化空间

总结

本题通过巧妙的容斥原理将复杂计数问题转化为树形DP问题，利用长链剖分优化空间复杂度，最终在 $O(nk)$ 时间内解决问题。代码实现较为复杂，但核心思想清晰：通过两次树形DP分别计算自底向上和自顶向下的信息，然后利用容斥原理得到最终答案。