题解：P10789 [NOI2024] 登山

· · 题解

题解

这是另一种比较好写的做法，只需要树剖。

首先考虑朴素的 DP，设 f_u 表示从 u 移动到点 1 的方案数，记 \mathrm{sub}_u 表示 u 子树内的点，\mathrm{anc}_u 表示 u 的所有祖先，有

f_u=\sum_{v\in \mathrm{sub}_u} \sum_{x\in \mathrm{anc}_u} \left[d_x<\min_{y\in \mathrm{path}_{u,v}} (d_y-h_y)\right] \left[d_x\in [d_v-r_v,d_v-l_v]\right] f_x.

其中 v 枚举的是滑落到了哪个点，x 枚举的是最后一次冲刺到了哪个点。如果固定 v，那么能转移到的 x 是 u 的祖先里深度在一个区间内的所有点。

困难之处在于，我们需要知道 u 的所有祖先的 f_v 才能算出 f_u，所以不能直接线段树合并维护子树内所有 v 的值。

考虑树剖，按照 DFS 序对每条重链算出 f_u。对于重链上每个点 u，我们需要维护出 \mathrm{sub}_u 中所有点对应的深度区间，也就是 [d_v-r_v,\min(d_v-l_v,\min_{y\in \mathrm{path}_{u,v}} (d_y-h_y-1))]。

在重链上从上往下维护这个是不好做的，但我们可以先从下往上做，然后再一步步地撤销。具体地，先从下往上枚举重链上的每个点 u，将 u 的所有轻子树内的点加入到数据结构中（这里可以将一个区间 [l,r] 拆成在 r 处贡献 1，在 l-1 处贡献 -1 的两个单点），然后再把数据结构内的所有点的下标对 d_u-h_u 取 \min，而取 \min 也可以拆成均摊 O(1) 个单点修改。

在撤销过程中，我们还需要询问数据结构中所有点对应的下标 k 的 \sum_{v\in \mathrm{anc}_u\land d_v\le k} f_v 之和。注意到刚才的修改只有单点修改，所以这也是容易维护的。

在这个过程中，数据结构需要支持的操作只有单点修改和查询最大的贡献非零的位置，所以直接用 map 维护即可。

因为所有轻子树大小之和是 O(n\log n) 的，所以我们总共会在 map 中插入 O(n\log n) 个点，总的时间复杂度是 O(n\log^2 n)。跑得很快。

代码

拿不到。