题目

点这里看题目。

你有一棵树 \(T\)，初始时 \(T=(V=\{1\},E=\varnothing)\)。

你将要进行 \(q\) 次操作，每次操作的形式为以下两种之一：

• 第一种操作：给定参数 \(x,y\)，保证 \(x\in V,y\not\in V\)。令 \(V\gets V\cup\{y\},E\gets E\cup\{(x,y)\}\)。
• 第二种操作：给定参数 \(x,y\)，保证 \(x,y\in V\)，求 \(T\) 生成的“谷图” \(G(T)\) 上 \(x,y\) 之间的最短路径经过的边数。

一棵树 \(T=(V,E)\)​​ 的“谷图” \(G(T)=(V,E')\)​​​，其中 \((u,v)\in E'\)​ 当且仅当在 \(T\)​ 中，任意的 \(u,v\)​​ 简单路径上非 \(u,v\)​ 的点的编号都不超过 \(\min\{u,v\}\)​。

所有数据满足 \(1\le n\le 10^5,1\le q\le 5\times 10^5\)​，其中 \(n\) 为 \(q\) 次操作结束后的 \(\max V\)。

分析

看到这个神秘的“谷图”，第一反应就是和关于点的 Kruskal 重构树相关。

但经过动手实践，直接把这个东西套上去并没有什么特别大的益处。所以，我们还是回到询问（显然这个问题的重心在询问上），想想一些简单的结论。

首先，\(x\)​ 要到 \(y\)​，最大的阻碍为 \(x,y\)​ 路径上除 \(x,y\)​ 以外的最大编号的点，记其为 \(z\)​。如果 \(x>z,y>z\)​，那么直接走过去就好了。否则，\(x\)​ 首先需要走到一个尽量大的点 \(x'\)​，如果不行继续走到一个尽量大的点 \(x''\)​......直到踩到的点 \(\ge z\)​ 为止。之后我们需要从 \(z\)​ 开始“下降”吗？显然不必这样思考——路径是对称的，我们可以将 \(y\)​ 也类似地持续拉升，直到 \(y\)​ 踩到的点 \(\ge z\) 位置。

所以，我们需要算出的就是：

从某个点 \(x\)​ 出发，每次走到 \(x\)​ 可以一步到达的编号最大的结点，求第一次所在编号 \(\ge z\)​​ ​时经过走过的步数。

很显然，\(x\)​​​ 走一步到达的编号最大的结点是确定的，我们记其为 \(\text{nxt}_u\)​​。​并且，容易发现 \(\text{nxt}_u\) 构成了一棵树，且该树满足堆性质。所以，如果我们可以维护好这棵树（称之为 \(T_2\)），我们就可以通过二分计算出答案。

回扣一下，这个 \(T_2\)，或者说 \(\text{nxt}_u\) 和点的 Kruskal 重构树有什么关系呢？

注意到：\(\text{nxt}_u\)​ 实际上是仅考虑 \(\le u\)​ 的结点时，\(u\)​ 能够到达的结点的邻接点中的编号最大值。或者说人话：从小到大加入点，加到 \(u\) 时，\(u\) 所在的连通块的所有邻接点的最大编号。

从原始连通块到连通块的邻接点，中间差了什么？就是那些连接邻接点的边！构建关于点的大根 Kruskal 重构树 \(T_1\)​​​，并考虑一条边 \((x,y)\in E\)​​​（不妨设 \(x<y\)​​​），将它在 \(T_1\)​ 中连上（很明显它必然是一条祖孙边）。由于 Kruskal 重构树中，\(u\)​ 的子树恰为“仅考虑 \(\le u\)​ 的结点时，\(u\)​​​ 能到达的所有结点”，所以 \(\text{nxt}_u\)​ 即为 Kruskal 重构树上 \(u\)​​ 子树内所有边的终点的最大值。

更进一步地，我们考虑整个过程中 \(T_1,T_2\) 的维护方式。

首先，考虑 \(T_1\)​。当我们加入 \((x,y)\)​ 这条边的时候，我们考虑 \(x\)​ 到根的链上的所有结点，\(y\) 只需要找到一个合适的位置插入即可。我们需要有序地拉出来一条到根的链，并执行二分——很显然，我们可以用 LCT 维护 \(T_1\)。

那怎么维护 \(T_2\)​​​​？加入一条边的操作相当于对于 \(x\)​​​​ 到根的链上的任一结点 \(z\)​​​​，都执行一遍 \(\text{nxt}_z\gets \max\{\text{nxt}_z,y\}\)​​​​。这样会导致——\(\text{nxt}_z\)​​​​​ 会是一段一段的样子，并且由深到浅也是单调不降的。那么，我们也可以一段一段地将 \(\text{nxt}\)​​​ 改为新值，并且被修改的 \(\text{nxt}\)​​​​ 必然是一段较深的后缀。这个操作类似于 LCT 的 Access 操作，因此均摊复杂度为 \(O(n\log n)\)​，具体分析过程并不清楚。

所以，我们已经搭好了一个 \(O(n\log^2n+q\log n)\) 的算法框架！