自动搬运

查看原文

来自洛谷，原作者为

	Larunatrecy 举杯邀明月，对影成三人。

搬运于2025-08-24 23:01:16，当前版本为作者最后更新于2024-07-21 21:05:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考场做法，写加调两个小时，应该算比较简单的做法。

我们先令 $l_i,r_i$ 表示可以冲刺到的点的深度范围，$lim_i=d_i-h_i-1$。

我们发现因为 $h_i\geq 0$，所以每次向上冲刺之后新的限制一定是当前点的 $lim_i$，那么就设 $dp_i$ 表示当前在节点 $i$，走到 $1$ 的方案数，那么一定是先向下滑到子树内某个节点 $j$，然后再跳到 $i$ 的某个祖先 $k$，那么 $k$ 应当满足：

• 设 $v_{i\to j}$ 为 $i\to j$ 路径上 $lim$ 的最小值，那么 $d_k\in [l_j,\min(r_j,v_{i\to j})]$。

枚举 $i$，枚举 $j$，用一个数组 $s$ 维护当前祖先链上 $dp$ 值的前缀和，即可做到 $O(n^2)$。

然后考虑一下 $l_i=r_i$ 的部分分，对于一个 $j$，满足 $r_j\leq v_{i,j}$ 的 $i$ 是祖先链上一段后缀，可以倍增出来，然后在求出来 $d_k=l_j$ 的点的 $dp$ 值后，对这段后缀做一个链加，可以求 dfs 序后树状数组维护，复杂度 $O(n\log n)$。

然后拓展到 $l_i\neq r_i$，依旧考虑对于一个 $j$，当 $i$ 再往上走的时候，$v_{i,j}$ 会改变的点实际就是所有后缀最小值的位置。

我们可以把贡献拆成 $s_{\min(r_j,v_{i\to j})}-s_{l_j-1}$，然后在求出来 $s_x$ 的时候考虑所有 $l_j-1=x$ 或者 $\min (r_j,v_{i,j})=x$ 的 $j$。

$s_{l_j-1}$ 的处理就是 $l_i=r_i$ 的部分，对于另一部分我们考虑对于一个 $j$，一定是先取一段 $r_j$，然后取到某个 $lim_u=v_{i,j}$ 的 $lim_u$，我们令 $u$ 为这些点里深度最大的（也就是严格的后缀最小值），那么我们枚举 $u$，发现此时 $i,j$ 独立，可以倍增求出 $w_u$ 表示上述的 $j$ 的个数，可以贡献到的 $i$ 也是一段祖先，依旧是一个链加。

$w_u$ 的求法：

对于每个 $i$，求出 $f_i$ 表示 $i$ 到根路径上第一个 $lim_j<lim_i$ 的 $i$，然后 $f_i$ 构成了一棵树，那么可以贡献到的 $w_u$ 构成了这棵新树上的一段祖先链，差分即可。

综上，我们只需用倍增和树状数组就在 $O(n\log n )$ 复杂度解决了这个题。