题解：P12403 [COI 2025] 象掌兽 / Lirili Larila

· · 题解

直接枚举 s,t 显然无法优化，我们想减少枚举量，考虑一种缩减操作：

对于树时的缩减，可以考虑把两个点往对方移动一步，那么只剩下 dis(s,t)\leq 2 的情况。

然后是基环树，我们发现如果两个点在同一环上不太能执行缩减，考虑如何直接做。 可以分为三种情况： - 无蓝色子树。\ 这种情况对应环长为偶数，子树各取一半的情况，很好做。 - 有一个蓝色子树。\ 环长为奇数，选一个点然后左右分一半。 - 两个蓝色子树。\ 根上面的类似，情况也很少，枚举蓝色子树位置。 若两个点都不在环上，可以向对方移一步，所以只剩下有一个点在环上的情况。 设不在环上那个点对应环上 $x$ 的子树。 若一个点覆盖了整个环，也可以将他们进行缩减，把一个点移到 $x$ 另一个点移动相应步数即可。 那么现在的情况就是两个点，分别对应了两段子树。 需要满足这些子树存在一个深度等于某个值的点，找到这个点后就能求出环上那个点了。 直接枚举区间肯定不行，但是我们要等于某个定值可以双指针扫出区间的大致范围然后再查询内部深度最大值，ST 表即可。 剩下的仙人掌依然考虑环 + 树的形式去做，检查在同一个环上（这部分和上面完全一样）的情况，剩下的也差不多，我们需要维护出距一个点最远的点，树形 dp 加换根即可。 时间复杂度 $\mathcal{O}(n\log n)$。