jumping sol.md

首先，如果你做过 BZ \(2144\)​，你可以发现一共只有：

• 中间的往左跳。
• 中间的往右跳。
• 两边的往中间跳。

第三个是对称的，我们不妨设他是 \(fa\)，前两个一个 \(ls\)，一个 \(rs\)。那么我们有一棵二叉树，现在要问从一个点到另一个点方案数。两个点设为 \(a,b\)。

和 \(2144\) 不同的是，\(k=100\) 非常的小。这个 \(\mathcal{O}(k^3)\) 都可以。

容易发现，离 \(a,b\) 太远的我们管都不用管。

有一种从 \(a\rightarrow b\) 的方法，就是 \(a\rightarrow lca(a,b)\rightarrow b\)，所以有一个想法是设 \(dp_{i,j}\) 为我们现在用了 \(i\) 步，在 \(j\) 深度方案数，但是我们发现这个有时候对不上。还有一个想法是设 \(dp_{node,i}\) 为我们现在在 \(node\) 节点，走了 \(i\) 步，但是状态数太多，很大便。

所以，尝试合并两种思路？我们发现有一个关键的路径（在 \(lca(a,b)\rightarrow b\) 尤其关键），就是 \(a\rightarrow lca(a,b)\rightarrow b\)。为啥关键呢？考虑一个不在关键路径上的点，只有可能往上走才能到关键路径。而：

• \(a\rightarrow lca(a,b)\) 这一段，我们拐到 \(lca(a,b)\) 之前要在关键路径上。
• \(lca(a,b)\rightarrow b\) 这一段，我们必须在关键路径上才可以到 \(b\)。

还有一个比较重要的性质，就是（因为一个不在关键路径上的点，只有可能往上走才能到关键路径），所以所有这种不关键的点我们只需要记录到关键点的距离，其他的信息不重要（这里有一点 \(2001E\) 的感觉）。

所以我们就有新的 \(dp_{i,j,k}\) 为：我们在关键点 \(i\) 子树内，和 \(i\) 距离 \(j\)，目前走了 \(k\) 步。转移比较简单。具体的：

• 若 \(j=0\)，则可以到 \(ls,rs,fa\)；如果 \(ls\) 是关键点则 \(dp_{i,0,k}+=dp_{ls,0,k-1}\)，否则 \(dp_{i,0,k}+=dp_{ls,1,k-1}\)，\(rs\) 同理（注意 \(fa\) 一定是关键点，如果有 \(fa\) 的话。有 \(fa\) 的条件是三个棋子不是等差数列）。
• 否则我们可以往下 \(j\leftarrow j+1\)，或者往上 \(j\leftarrow j-1\)。注意往下有两个儿子，加贡献的时候要 \(\times 2\)。

还有一个小细节。就是如果 \(a\rightarrow lca(a,b)\rightarrow b\) 长度 \(<k\)，我们还有可能会走到 \(lca(a,b)\) 上面再回来。因此我们设 \(2k\) 个关键点，分别是 \(a,b\) 的 \(0\sim k-1\) 级祖先即可。

dp 用记忆化搜索比较好写。时间复杂度 \(\mathcal{O}(k^3)\)。