P10789 [NOI2024] 登山
思路：我们可以对于每个 \(i\) 找到它能跳到的最远的点和最近的点，倍增求一下 \(k\) 级祖先即可，令 \(\) 新表示 \(i\) 能跳到其祖先中深度在 \(\) 内的点；同时令 \(lim_i = d_i - h_i-1\) 表示 \(i\) 至少要跳到 \(lim_i\) 的深度。
考虑动态规划算法，令 \(dp_i\) 表示从 \(i\) 出发到山顶的合法登山序列个数。
那么相当于先从 \(i\) 滑落到 \(j\)，然后再从 \(j\) 冲刺到 \(k\)，再加上 \(dp_k\) 的方案数。
则状态转移方程为：
\) dp_k\]
其中 \(W(i,j)\) 表示 \(i \to j\) 路径上 \(lim_k\) 的最小值，因为每次冲刺到达的深度必须小于所有经过的点的 \(lim_k\)。
朴素实现是 \(O(N^3)\) 的，考虑优化；注意到 \(k\) 是 \(i\) 的祖先中一段深度连续的点，则我们可以做一个深度的 \(dp_i\) 的前缀和，差分即可，时间复杂度优化至 \(O(N^2)\)，可以得到 25pts。
$O(N^2)$ Code： namespace Sub1{ ll L,R,x,a,b; ll s,dp,dep; void dfs1(ll u){ for(auto v:E){ if(v==fa) continue; dep=dep+1; dfs1(v); } } ll get(ll l,ll r){ if(!l) return s; return (s-s+mod)%mod; } void dfs3(ll u,ll Min,ll from){ L=l,R=min(r,Min); if(L1; build(k 新版吗？好像是停更了吧。 感谢分享，学习下。 感谢分享，下载保存了，貌似很强大 收藏一下 不知道什么时候能用到 分享、互助 让互联网精神温暖你我 感谢分享，下载保存了，貌似很强大 不错，里面软件多更新就更好了 懂技术并乐意极积无私分享的人越来越少。珍惜 东西不错很实用谢谢分享 用心讨论，共获提升！ 这个好，看起来很实用 不错，里面软件多更新就更好了 这个好，看起来很实用 这个有用。 yyds。多谢分享 新版吗？好像是停更了吧。 收藏一下 不知道什么时候能用到 感谢分享，学习下。 不错，里面软件多更新就更好了
页:
[1]
2