hack 数据

针对错误 LCT 写法的 hack 数据。

百度网盘链接。

---

关于这两篇讨论 (1)，(2) 中提到的问题：

很多 LCT 题解使用下列做法寻找 splay 最左边的点：

int findroot(int x)
{
    while(ch[x][0]) x = ch[x][0];
    return x;
}

由于此题不能在 findroot 后 splay，导致复杂度会达到 $O(n^2)$ 级别，这样是错误的，正确做法应该是维护子树内深度最浅的点的编号 （并且是很容易的）。

hack 方式

首先构造树：一条链顶为 $1$，有 $n−1$ 个节点的链，设链底为 $p$，然后 $1$ 旁边接一个节点 $x$。

构造一棵左倾严重的 Splay：从链顶到链底依次 Access，由于次数限制，数据中 Access 了 $O(\displaystyle\frac{m}{3})$ 个点，取链自上而下第 $O(\displaystyle\frac{m}{3})$ 个点作为 $p$。

不断 Access(x); Access(p) 交替作为操作，此时一次 Access(p) 中 findroot 的复杂度达到 $O(\displaystyle\frac{m}{3})$。

设 $n,m$ 同阶，时间复杂度 $O(n^2)$。

实际测试了几篇 LCT 题解，findroot 中循环执行次数为 $1111055555$ 次。