[COI 2025] 象掌兽 / Lirili Larila 题解
题目传送门： 象掌兽 / Lirili Larila。我宣布 夏虫 和 rgxsxrs 的代码难度在这题面前都弱爆了。
下面的题解几乎完全复制了模拟赛的出题人的题解，稍微修改了一些小错误并加上了一些细节。但是因为我不知道出题人是谁，所以无法 @ 出他，对此我深感抱歉。如果这位出题人看到了这篇博客麻烦告知一下，我方便指出出处。顺便让我知道一下是哪位毒瘤把这个东西放 T2。
算法一
我会暴力！
枚举 \(s,t\) 然后 \(O(n + m)\) BFS 跑最短路并判断。
时间复杂度 \(O(n^2(n + m))\)，期望得分 \(6\)。
算法二
我会树！
以下称 \(dis(s, u) < dis(t, u)\) 的点为 \(A\) 类点，\(dis(s, u) > dis(t, u)\) 的点为 \(B\) 类点，\(dis(s, u) = dis(t, u)\) 的点为 \(C\) 类点。
若 \(dis(s, t) \ge 3\)，那么让 \(s\) 和 \(t\) 分别朝向对方移动一步，所有点的类别不变。所以只用考虑 \(dis(s, t) \le 2\) 的情况。
若 \(dis(s, t) = 1\)，枚举这条边，那么 \(A\) 类点在 \(s\) 子树内，\(B\) 类点在 \(t\) 子树内。
若 \(dis(s, t) = 2\)，枚举路径中点 \(x\)，那么以 \(x\) 为根，\(x\) 的所有子树中，恰好有一棵子树，其中所有点都是 \(A\) 类点，恰好有一棵子树，其中所有点都是 \(B\) 类点。其他点都是 \(C\)类点。
时间复杂度 \(O(n)\)，结合算法一期望得分 \(39\)。
算法三
我会基环树且 \(s,t\) 都在环上！
设环长为 \(l\)。若 \(l\) 是奇数，那么环上有长度为 \(\frac{l−1}{2}\) 的一段子树都是 \(A\) 类点，有长度为 \(\frac{l−1}{2}\) 的一段子树都是 \(B\) 类点，恰好有一棵子树是 \(C\) 类点。
若 \(l\) 是偶数，有两种情况。
第一种情况是环上有长度为 \(\frac{l}{2}\) 的一段子树都是 \(A\) 类点，有长度为 \(\frac{l}{2}\) 的一段子树都是 \(B\) 类点，没有 \(C\) 类点。
第二种情况是环上有长度为 \(\frac{l}{2}−1\) 的一段子树都是 \(A\) 类点，有长度为 \(\frac{l}{2}−1\) 的一段子树都是 \(B\) 类点，两个区间之间有两棵子树是 \(C\) 类点。
枚举选的 \(A\) 类点子树区间然后讨论 \(C\) 类点子树的位置即可确定 \(B\) 类点子树区间。
时间复杂度 \(O(n)\)，结合算法一和算法二期望得分 \(56\)。
算法四
我会基环树！
若 \(s,t\) 的路径不经过环，用树的做法即可。
若 \(s,t\) 的路径经过环，且 \(s\) 和 \(t\) 都不在环上，那么让 \(s\) 和 \(t\) 分别朝向对方移动一步，所有点的类别不变。所以只用考虑 \(s\) 和 \(t\) 至少有一个在环上的情况。
若在环上的点为 \(t\)，设 \(s\) 在环上点 \(x\) 的子树内，那么需要满足 \(s\) 到 \(x\) 的最短路小于等于 \(t\) 到 \(x\) 的最短路，否则同样可以通过移动归约为 \(s,t\) 的路径不经过环的情况。反之亦然。
发现此时点的类别的情况和 \(s,t\) 都在环上的大致相同。设环长为 \(l\)。
若 \(l\) 是奇数，那么环上有长度为 \(k (1 \le k \le l − 2)\) 的一段子树都是 \(A\) 类点，有长度为 \(l − 1 − k\) 的一段子树都是 \(B\) 类点，恰好有一棵子树是 \(C\) 类点。
若 \(k \le l − 1 − k\)（如上图），那么 \(t\) 在环上。我们需要在 \(A\) 类子树找一个到环的距离 \(=\frac{l−1−2k}{2}\) 的点（可以用 ST 表查询区间最大值位置求出在哪棵子树内）。然后根据 \(s\) 在哪棵子树内就可以确定 \(t\) 的位置。
\(k > l − 1 − k\) 的情况无非就是变成 \(s\) 在环上，交换一下 \(A,B\) 再做一遍即可。
若 \(l\) 是偶数，有两种情况。
第一种情况是环上有长度为 \(k (1 \le k \le l − 1)\) 的一段子树都是 \(A\) 类点，有长度为 \(l − k\) 的一段子树都是 \(B\) 类点，没有 \(C\) 类点。
若 \(k \le l − k\)（如上图），那么 \(t\) 在环上。我们需要在 \(A\) 类子树找一个到环的距离 \(=\frac{l−2k}{2}\) 的点。\(k > l − k\) 的情况大致相同。
第二种情况是环上有长度为 \(k (1 \le k \le l − 1)\) 的一段子树都是 \(A\) 类点，有长度为 \(l − 2 − k\) 的一段子树都是 \(B\) 类点，两个区间之间有两棵子树是 \(C\) 类点。
若 \(k \le l − 2 − k\)（如上图），那么 \(t\) 在环上。我们需要在 \(A\) 类子树找一个到环的距离 \(=\frac{l−2−2k}{2}\) 的点。\(k > l − 2 − k\) 的情况大致相同。
以上情况都可以枚举 \(A\) 类子树区间的左端点然后双指针出第一个满足区间子树和 \(\ge A\)（这个 \(A\) 是题面给的 \(A\)） 的右端点，讨论 \(C\) 类点子树的位置即可确定 \(B\) 类点子树区间，从而算出 \(t\) 的位置。
不过有一种特殊情况。
不妨设在环上的点为 \(t\)，设 \(s\) 在环上点 \(x\) 的子树内，则特殊情况为 \(t\) 到 \(x\) 的最短路恰好等于 \(s\) 到 \(x\) 的最短路。此时环上恰好有一段 \(C\) 类点和一段 \(B\) 类点。特别地，\(x\) 往 \(s\) 方向的子树是 \(A\) 类点，\(x\) 的其他子树是 \(C\) 类点。
此时我们去双指针 \(B\) 类点子树区间，并讨论 \(x\) 是在这个区间的左边还是右边，设这个区间长度为 \(k\)，环长为 \(l\)。那么 \(s\) 到 \(x\) 的距离需要等于 \(x\) 到 \(t\) 的距离也就是 \(k−\lfloor \frac{l−1}{2} \rfloor+1\)（注意这个时候得 check 一下 \(x\) 是否真的有大小为 \(A\) 的子树）。
时间复杂度 \(O(n \log n)\)，结合算法一和算法二期望得分 \(77\)。
算法五
我会正解！
考虑直接把树和基环树的想法结合起来。
先考虑 \(dis(s, t) = 1\) 且 \(s, t\) 不在同一个环的情况。再考虑 \(dis(s, t) = 2\) 且若设 \(x\) 为 \(s\) 到 \(t\) 路径中点则 \(s, x, t\) 都不在同一个环内的情况。
接下来的想法和基环树类似。若 \(s,t\) 两个点都不在环上，那么让 \(s\) 和 \(t\) 分别朝向对方移动一步，所有点的类别不变。
所以枚举一个环使得 \(s, t\) 至少有一个在这个环上。不妨设 \(t\) 在环上，\(x\) 为 \(s\) 到这个环的必经点，那么需要满足 \(s\) 到 \(x\) 的最短路小于等于 \(t\) 到 \(x\) 的最短路。
对原图建出圆方树后，我们需要求出每个点 \(u\) 子树内（记作 \(d_1\)）和子树外（记作 \(d_2\)）所有点到 \(u\) 的最短路的长度最大值。可以通过换根 DP 求出。
换根时，圆点向方点的转移是简单的，只需要处理一下儿子的 \(d_1\) 的前缀和后缀 \(\max\) 即可快速转移。
在方点向圆点转移时，如果这个方点代表的环上的点是 \(u_1,u_2,...,u_l\) 要转移的原点是 \(u_i\)，相当于是说我们要求 \(\max_{j\ne i} (min(|i − j|, l − |i − j|)+d(a_j))\)，其中 \(d(u)\) 表示点 \(u\) 在环以外的子树的最大深度（根据他的位置可能是 \(d_1\) 也可能是 \(d_2\)）。用 ST 表维护区间 \(d(a_j)+j\) 和 \(d(a_j)-j\) 的最大值，转移时根据 \(|i − j|\) 和 \(l − |i − j|\) 的关系分成两部分转移即可。
接下来的讨论和算法四的部分没有区别，故不赘述。
时间复杂度 \(O(n \log n)\)，期望得分 \(100\) 分。
点击查看代码#include#define Debug puts("-------------------------")#define eb emplace_back#define P pair #define PII pair#define fi first#define se second #define mk make_pair#define None mk(mk(0,mk(0,0)),0)using namespace std;const int N=2e5+5,M=4e5+5,inf=0x3f3f3f3f;inline int read(){ int w=1,s=0; char c=getchar(); for(;c'9';w*=(c=='-')?-1:1,c=getchar()); for(;c>='0'&&c
页:
[1]