[NOI2024] 登山，从性质一步步切入正解的典型题目

forest114514 · 2024-07-25 16:37:35 · 题解

upd：晚上突然想到某一步分析错了，修改了一下。

场外弱鸡选手 VP 的时候成功口胡出了这道题，却因为代码能力太差了成功编程半小时，调试一上午……

本题个人认为部分分设置是非常好的！本蒟蒻也是在部分分的启发下才能很快想出正解做法，所以本题解也侧重于讲述如何从部分分入手一步步想到正解。

• 最暴力的部分

  注意到我们行动的阶段是首先从一个点 u 的子树某一个点出发冲刺到 u 的一个祖先处，然后变成了一个子问题，因为每次冲刺到的点深度单减，所以可以 DP。

  设 f_{u} 为 u 出发走到 1 的方案数，每次枚举从子树哪个点出发，走到哪个祖先即可，则有：

  f_{u}=\sum\limits_{v\in subtree_{u}}\sum\limits_{p\in ancestor_{u}}[dep_{p}\in [dep_{v}-r_{v},dep_{v}-l_{u}]\land dep_{p}<\min \limits_{i\in path(u,v)}(dep_{i}-h_{i})] f_{p}

  直接是 O(n^3) 的，发现每个 v\in subtree_{u} 的能走到的 p 是一条链，差分一下求链上前缀和就能做到 O(n^2)（此时发现 l_i=r_i 的性质似乎没有什么意义？）。

  现在直接对着这个式子优化不容易，我们先想想特殊性质，这个策略在赛场上也是正确的。

• 树是一条链

  这是最简单的部分，因为从序列问题的难度一般比树上问题低得多。

  假设我们已经求出了 f_{i} 的答案，我们能不能快速求出 f_{i+1} 的答案呢？

  考虑 f_{i} 的答案有两部分：i 出发的部分和 [i+1,n] 出发的部分；f_{i+1} 的答案只有 [i+1,n] 出发的部分，所有部分都是若干前缀和查询。

  但是 f_{i} 和 f_{i+1} 对于 [i+1,n] 出发的部分有一点不一样，前者的 \min \limits_{j\in path(u,v)}(dep_{j}-h_{j}) 会有 dep_{i}-h_{i} 的限制，所以考虑加上这个限制之后的变化，其实把某一些 >dep_{i}-h_{i}-1 的查询变成了 dep_{i}-h_{i}-1。

  其实我们可以暴力统计，因为对查询的取 \min 后每次只会新增 O(1) 个本质不同的深度，而每个深度只会被删除一次，所以均摊是 O(n) 的，那直接用一个能统计有序二元组，删除一段值域区间时间复杂度为 O(\text{点数}) 的数据结构就行了，可以用堆或平衡树，简单起见用 std::map 即可，时间复杂度 O(n\log n)。

• h_{i}=0

  这样其实每个子树出发时 \min \limits_{j\in path(u,v)}(dep_{j}-h_{j}) 的限制就是 dep_{p}<dep_{u}，此时 h 的限制几乎没有作用了。

  首先类比链的做法，已知 u 递推其所有儿子的答案，但是 u 会有其所有儿子的贡献，不好直接递推，但我们可以考虑树上启发式合并，可以直接暴力计算 u 所有轻子树的 f 值和贡献，最后用 f_{u} 减去 u 的贡献和 u 所有轻子树的贡献就得到了重子树的贡献，考虑 h_{i}=0 的时候每次对 dep_u-1 取 \min 只会有 dep_{son_{u}}-1 的询问发生变化，所以变化时严格 O(n) 的，可以借鉴链性质的部分维护重子树的变化量，只是在原做法上套了一个 dsu on tree，此时时间是 O(n\log ^2n) 的，如果 std::map 换成平衡树+finger search 能做到 O(n\log n)。

• 正解

  其实 h_i=0 的部分和 h_i\geq 0 差了一个性质就是每次重儿子对 dep_{i}-h_{i}-1 取 \min 时变化的点只有严格 O(1) 的，而借用链部分的均摊 O(n) 的做法似乎难以说明树上能均摊 O(n) 次改变，但其实是可以的。

  考虑我们只用记录重儿子在对 dep_{u}-h_{u}-1 取 \min 时候的有哪些点被修改了，而借用重链剖分的理论其实就是我们对一条重链做了链部分类似的操作，考虑每次修改类似于区间推平，然后加 O(1) 个点，所以一条重链均摊下来修改操作有 O(\text{链长}) 次，所以树上的操作均摊还是 O(n) 次删除，可以记录下来。

  如果像我一样偷懒写 std::map 暴力修改+暴力启发式合并的话时间是 O(n\log ^2 n) 的，空间的话是 O(n) 的，只不过在 std::map 的加持下还是有 40MB 的空间。

  这个做法常数很小，在我 #define int long long 这个常数炸弹的加持下最慢点也才 280ms。

至于 l=r 的部分因为我做的时候还没看就想到正解就没写了……

因为一直调不出来导致十分难看的代码