题解：P13567 「CZOI-R5」折跃点

Reply_ · 2025-08-04 20:57:07 · 题解

题解：P13567 「CZOI-R5」折跃点

观察题面，注意到一个重要条件：“且过程中与折跃点 1 的距离不断增加或不断减少。”

那么只能往上或者往下一直走，即对于点 u，经过 x 次折跃后能到达的点是 v，v 需要满足的条件有两种。

• 向上走，v 是 u 的祖先，而且 dep_v=dep_u-x。
• 向下走，v 在 u 的子树内，而且 dep_v=dep_u+x。

第一种条件较为简单，直接倍增向上跳找到即可。

第二种条件较为复杂，因为满足第二种条件的点会有多个，考虑对于每一个深度维护线段树，每个点向下走能达到的点在线段树是一个连续的区间，以每个点的 dfs 序为索引，因为一个点的子树的 dfs 序是一个连续区间，可以用二分求出这个区间在某棵线段树上对应的区间进行修改或者查询即可。

代码很丑就不贴了。