D. Tree Jumps 详细题解

问题理解

我们有一棵以 $1$ 为根的有根树，每个顶点 $v$ 的距离 $d_v$ 定义为从根到 $v$ 的边数（根的距离为 $0$）。

初始时棋子在根节点 $1$。每次操作可以将棋子从当前节点 $v$ 移动到某个节点 $u$，满足 $d_u = d_v + 1$（即必须往下一层走），并且：

• 如果 $v$ 是根节点，可以跳到下一层的任意节点
• 如果 $v$ 不是根节点，则 $u$ 不能是 $v$ 的邻居（即不能是 $v$ 的父节点或子节点）

注意：由于 $d_u = d_v + 1$，$u$ 只能是 $v$ 的孩子节点或下一层的其他非孩子节点。但“不能是邻居”这个条件禁止跳到孩子节点（因为孩子是邻居），所以当 $v$ 不是根时，只能跳到下一层中不是自己孩子的节点。

一个顶点序列被称为有效，如果存在一种移动方式，使得棋子按顺序访问序列中的所有顶点（且只访问这些顶点，不能多也不能少）。

求所有有效序列的数量，对 $998244353$ 取模。

---

关键观察

1. 序列必须从根开始

因为棋子初始在根，且只能向下走（$d_u = d_v + 1$），所以任何有效序列的第一个顶点必须是根 $1$。

2. 序列中顶点的深度严格递增

每次操作深度 $+1$，所以序列中顶点的深度必须严格递增：$d_{v_1} < d_{v_2} < \dots$。
因此，一个有效序列对应一条从根出发的“路径”，但这条路径不一定是树上的连续路径，因为可以跳到非孩子节点。

3. 移动规则的本质

设当前在深度 $i$ 的节点 $v$，要跳到深度 $i+1$ 的节点 $u$：

• 如果 $i = 0$（即 $v$ 是根）：可以跳到深度 $1$ 的任意节点
• 如果 $i \ge 1$：可以跳到深度 $i+1$ 中除了 $v$ 的孩子以外的任意节点

换句话说，从深度 $i$ 的一个节点出发，能够到达的深度 $i+1$ 节点集合 = 整个深度 $i+1$ 的节点集合，减去该节点的孩子集合（当 $i \ge 1$ 时）。

---

动态规划思路

设 $dp_v$ 表示以顶点 $v$ 结尾的有效序列的数量。

那么答案就是 $\sum_{v} dp_v$。

边界条件

$dp_1 = 1$，因为序列 $[1]$ 是有效的。

转移方程

对于非根节点 $v$（深度 $d_v = i \ge 1$），考虑它的所有可能前驱节点 $p$（深度为 $i-1$ 的节点），使得从 $p$ 可以合法地跳到 $v$。

从 $p$ 跳到 $v$ 合法的条件是：

• 如果 $i-1 = 0$（即 $p$ 是根）：总是合法
• 如果 $i-1 \ge 1$：需要 $v$ 不是 $p$ 的孩子

所以：

$$dp_v = \sum_{p \in \text{depth } i-1} [\text{可以从 } p \text{ 跳到 } v] \cdot dp_p $$

令 $S_{i-1}$ 表示深度 $i-1$ 的所有节点，$total_{i-1} = \sum_{p \in S_{i-1}} dp_p$。

那么：

• 如果 $i-1 = 0$（即 $i=1$）：$dp_v = total_0 = 1$（因为深度 $0$ 只有根，$dp_1=1$）
• 如果 $i-1 \ge 1$：$dp_v = total_{i-1} - \sum_{p \text{ 是 } v \text{ 的父节点}} dp_p$

注意：一个节点 $v$ 的父节点是唯一的，设为 $f(v)$。所以 $\sum_{p \text{ 是 } v \text{ 的父节点}} dp_p = dp_{f(v)}$。

因此，对于深度 $i \ge 2$ 的节点 $v$：

$$dp_v = total_{i-1} - dp_{f(v)}$$

其中 $total_{i-1} = \sum_{u: d_u = i-1} dp_u$。

---

算法步骤

1. 读入树，计算每个节点的深度 $d_v$
2. 按深度分组，得到每层的节点列表 vs[d]
3. 初始化：
   • $dp[1] = 1$
   • $total[0] = 1$
4. 按深度 $i$ 从 $1$ 到最大深度遍历：
   • 对于当前层的每个节点 $v$：
     • 如果 $i = 1$（$v$ 在深度 $1$）：$dp[v] = total[0] = 1$
     • 如果 $i \ge 2$：$dp[v] = total[i-1] - dp[parent[v]]$（模意义下）
   • 计算 $total[i] = \sum_{v \in vs[i]} dp[v]$
5. 答案 = $\sum_{i} total[i]$（即所有 $dp$ 之和）

---

正确性证明

归纳法：假设对于深度 $i-1$ 的所有节点，$dp$ 值已正确计算（表示以该节点结尾的有效序列数）。

对于深度 $i$ 的节点 $v$，所有以 $v$ 结尾的有效序列，去掉最后一个节点 $v$ 后，得到的是一个以某个深度 $i-1$ 节点 $p$ 结尾的有效序列，并且从 $p$ 可以合法跳到 $v$。

• 如果 $i=1$：$p$ 只能是根，且根可以跳到任意深度 $1$ 节点，所以 $dp_v = total_0 = 1$。
• 如果 $i \ge 2$：$p$ 可以是深度 $i-1$ 的任意节点，除了 $v$ 的父节点（因为不能从父节点跳到子节点）。所以 $dp_v = total_{i-1} - dp_{parent(v)}$。

因此转移正确。

---

复杂度分析

• 计算深度：$O(n)$
• 按深度分组：$O(n)$
• 每层遍历：$O(n)$
• 总时间复杂度 $O(n)$，每个测试用例
• 所有测试用例 $n$ 之和 $\le 3\times10^5$，完全可行

---

示例验证（以第一个样例为例）

树结构：$n=4$，父节点列表 $p_2=1, p_3=2, p_4=1$
深度：$d_1=0$，$d_2=1$，$d_3=2$，$d_4=1$

• 深度 $0$：$vs[0] = \{1\}$，$dp[1]=1$，$total[0]=1$
• 深度 $1$：$vs[1] = \{2,4\}$
  • $dp[2] = total[0] = 1$
  • $dp[4] = total[0] = 1$
  • $total[1] = 1+1=2$
• 深度 $2$：$vs[2] = \{3\}$，父节点 $parent[3]=2$
  • $dp[3] = total[1] - dp[2] = 2 - 1 = 1$
  • $total[2] = 1$

答案 = $total[0]+total[1]+total[2] = 1+2+1 = 4$，匹配输出。

---

总结

本题的核心是：

1. 观察到移动规则等价于：从深度 $i$ 的非根节点，可以跳到下一层的任意节点，除了自己的子节点
2. 使用按深度分层的 DP，转移时用“当前层总和减去父节点贡献”
3. 避免 $O(n^2)$ 的枚举，通过维护 $total[i]$ 实现 $O(n)$ 转移

这种“总合法前驱减去非法前驱”的技巧在树形 DP 中非常常见。