本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-17 10:13:32

题传

首先，我们可以想到，将 $i$ 向 $a_i$ 连边，表示球 $i$ 在盒子 $a_i$ 中。

这样我们就得到了一棵基环内向树。

我们考虑每次对盒子 $i$ 操作在干什么。

其实就是把所有连向 $i$ 的点拿出来，按任意顺序连成一个环。

但是我们考虑，每次连成环的过程中，我们无法得知应该按怎样的顺序去排列环，而且我们并不知道这张图的初始状态是怎样的，所以我们考虑倒着操作。

考虑将 $i$ 从 $n$ 到 $1$ 枚举的过程中，每次如何变化这张图。

实际上就是每次把一个环全部断开，然后全都连到 $i$ 上。

但是这样做是有问题的。

我们在正着做的时候，由于我们每次拿出了所有连向 $i$ 的点，所以每次对于 $i$ 操作完，点 $i$ 一定要么入度为 $0$，要么处在某一个环上，且除了环上的点没有点连向他，这就限制了我们每次操作 $i$ 的时候，必须保证当前图满足操作后的条件。

那么可以想到，如果我们在操作过程中发现当前的 $i$ 不合法，那么肯定就无解了。

那么我们每次应该操作哪个环才能最优呢？

我们考虑每次断开的环如果不在当前连通块，那么每个点的可操作性是不变的（可以自己画一画）；如果在当前连通块，那么我们发现，原来可操作的还能操作，如果当前点入度为 $0$，原来一些在当前点到环的路径上的点，可能从不能操作变为可操作，所以证明，我们每次操作当前连通块内的环一定是最优的。

所以我们可以暴力扫，每次找到当前环，然后暴力更改。

这样做乍一看是 $O(n^2)$ 的，实际上可以分析到 $O(n\sqrt n)$，可以均摊。

我们令环长为 $L$，每次的花费实际上就是 $O(L)$ 的。（可能还会多一点环之前的链，但是由于操作一次后链就变成环了，所以我们认为这还是环）。

总花费是 $O(\sum L)$ 的。

设 $S$ 为当前图上每个点的入度的平方和，显然，$S\le n^2$。

我们考虑操作一次后，$S$ 是如何变化的，对于原来在环上的点，它们的入度 $-1$；对于 $i$，他的入度 $+L$。

我们令 $ind_i$ 表示 $i$ 节点的入度，那么 $S$ 的变化就是 $(ind_{i}+L)^2+\sum_{\text{x on ring}} (ind_x-1)^2-ind_i^2-\sum_{\text{x on ring}} ind_x^2=L^2+2\times ind_i\times L-\sum_{\text{x on ring}} 2\times ind_x+1$。

所以 $S$ 的变化每次是 $O(L^2)-O(n)$ 的。

要变化 $n$ 次，那么 $\sum L^2$ 最多是 $O(n\sqrt n)$ 级别的。

实际上跑的飞快。

更详细的证明可以看这里。

感谢 @KSCD_ 和 @Pigsyy 的帮助。

提交记录。