题解：P10789 [NOI2024] 登山

Larunatrecy · 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。