题解

思路

原图是一棵从父亲指向儿子的树，并且父亲编号总小于儿子编号。一次新增操作中的 $v$ 是 $u$ 的祖先。树上路径 $v\rightsquigarrow u$ 原本可以向下走，而新边 $u\to v$ 又能回到路径顶端，所以这条路径上的所有点从此属于同一个强连通块。

反过来，新增边不会让任何点越过这条祖先链向更高处走。因此，每个点能到达的最小编号，恰好是它当前所在强连通块中最高的祖先。只需维护这些被逐步合并的树上路径。

做法

子任务 1：显式搜索

在 $N,Q\le2000$ 时，直接保存原树边和每次新增的边。遇到询问，从 $x$ 出发遍历当前有向图，并在所有访问到的顶点中取最小编号。

单次询问复杂度为 $O(N+Q)$，总复杂度为 $O(Q(N+Q))$，空间复杂度为 $O(N+Q)$。

子任务 2：链上的区间合并

当 $p_i=i$ 时，原树是一条链。每个当前强连通块都是一个连续区间；加入 $u\to v$ 会删除区间 $(v,u]$ 内的所有块边界。

用有序集合保存每个强连通块的左端点。更新时从集合中找到第一个大于 $v$ 的端点，依次删除所有不超过 $u$ 的端点；询问 $x$ 时，答案就是集合中不大于 $x$ 的最大端点。每个端点至多被删除一次。

总复杂度为 $O((N+Q)\log N)$，空间复杂度为 $O(N)$。

子任务 3：树上路径并查集

为每个顶点维护一个并查集代表。代表始终取该强连通块中最高的顶点。

处理 1 u v 时，先分别找到 $u,v$ 当前所在块的代表。只要二者不同，就把 $u$ 所在块的代表合并到它在原树中的父亲所在块，然后继续。由于 $v$ 是 $u$ 的祖先，这个过程一定沿祖先方向结束。

每次循环都会永久减少一个强连通块；全部操作中循环总次数不超过 $N-1$。询问 2 x 时，并查集代表就是答案。父亲编号严格更小，所以代表也必然是块内最小编号。

总复杂度为 $O((N+Q)\alpha(N))$，空间复杂度为 $O(N)$。

复杂度

• 子任务 1：总时间 $O(Q(N+Q))$，空间 $O(N+Q)$。
• 子任务 2：总时间 $O((N+Q)\log N)$，空间 $O(N)$。
• 子任务 3：总时间 $O((N+Q)\alpha(N))$，空间 $O(N)$。

正确性证明

首先证明每次新增边只合并 $v$ 到 $u$ 的树上路径。路径原有的向下边与新加入的 $u\to v$ 组成有向环，因此路径上任意两点互相可达。路径之外不存在由这条新边产生的向上出口，所以不会额外合并更高祖先。

并查集循环每次把当前 $u$ 块与其父亲块合并，恰好消去祖先路径上的一条尚未合并的边；当 $u,v$ 的代表相同时，整条路径已经合并。由归纳可知，并查集的每个集合始终恰好对应当前图的一个强连通块。

从一个强连通块可以沿原树边到达后代块，却不能因此到达更小编号；能向上到达的顶点全在自身强连通块内。故可达顶点的最小编号就是该块最高顶点的编号，也就是并查集代表。算法对每次询问的回答正确。