问题定义

给定一棵 $n$ 个节点的树，要求选择一个节点集合 $S$，使得对于任意 $u, v \in S$，$dist(u, v) \ge d$。求 $|S|$ 的最大值。

---

核心观察

在树结构中，距离约束可以转化为：如果选择节点 $u$，那么 $u$ 的 $d-1$ 邻域内不能选择其他节点。

---

树形 DP 状态设计

我们定义状态 $(dp[u], rest[u])$：

• $dp[u]$：以 $u$ 为根的子树中最多能选择的节点数
• $rest[u]$：该子树中距离 $u$ 最近的已选节点到 $u$ 的距离（如果没有已选节点，$rest[u] = \infty$）

但实际上我们不需要显式存储 $dp[u]$，而是维护一个全局答案。

---

关键算法

我们使用 DFS 后序遍历，为每个节点 $u$ 计算 $rest[u]$：

对于叶子节点 $u$：

• $rest[u] = 0$（我们可以选择叶子节点）

对于内部节点 $u$：

1. 收集所有子节点的 $rest$ 值，得到列表 $R = \{rest[v] + 1 \mid v \in children(u)\}$
2. 设 $min\_r = \min(R)$，$max\_r = \max(R)$
3. 如果 $min\_r \ge d$：
   • 选择节点 $u$，答案 $+1$
   • $rest[u] = 0$
4. 否则如果 $max\_r \ge d$：
   • 选择节点 $u$，答案 $+1$
   • $rest[u] = 0$
5. 否则：
   • $rest[u] = max\_r$

根节点特殊处理：

处理完根节点后，如果 $rest[0] \ge 0$（即根节点还没有被选择但可以被选择），答案再 $+1$。

---

算法正确性解释

1. 当 $min\_r \ge d$ 时：所有子树的最近已选节点都距离 $u$ 至少 $d$，选择 $u$ 不会违反约束。

2. 当 $max\_r \ge d$ 时：至少有一个子树的最近已选节点距离 $u$ 足够远，但更重要的是，这个条件意味着选择 $u$ 能够获得更好的解。

3. 否则：我们保留距离 $u$ 最远的已选节点信息，为父节点的决策提供便利。

---

时间复杂度

• 每个节点处理一次：$O(n)$
• 总时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

---

公式化表示

设 $C(u)$ 为 $u$ 的子节点集合，则：

$$rest[u] = \begin{cases} 0 & \text{if } u \text{ is leaf} \\ 0 & \text{if } \min_{v \in C(u)} (rest[v] + 1) \ge d \\ 0 & \text{if } \max_{v \in C(u)} (rest[v] + 1) \ge d \\ \max_{v \in C(u)} (rest[v] + 1) & \text{otherwise} \end{cases} $$

在选择节点 $u$ 时，全局答案增加 $1$。

---