给定的图是一个基环树森林，在不修改 $a_i$ 的情况下，最多能抓到的人数显然是取一个连通块，任取一个环上的点作为根，$\mathrm{dep}_u\bmod k=x$ ($0\le x< k$，$k$ 为环长) 的点数的最大值。要修改 $j$ 个 $a_i$，显然我们有两种决策：

• 连接 $j$ 个连通块，并且造一个自环，价值就是这些连通块大小的和。取所有连通块中最大的 $j$ 个即可。
• 连接 $j+1$ 个连通块，设最后的环长为 $k$，则每棵树的贡献就是 $\mathrm{dep}_u\bmod k=x$ ($0\le x< k$) 的点数的最大值。取其中最大的 $j+1$ 个即可，但其中至少要有一个环长为 $k$ 的。

在第二种情况中，注意根的选择是有影响的，但我们可以枚举所有根，每次的变化实际就是一棵子树的深度全部增加 $k'$ ($k'$ 是这个连通块的环长)，并且每次答案只会改变 $1$，因此可以 $O(n)$ 计算每个连通块对某个 $k$ 的贡献。环长的种数只有 $O(\sqrt n)$，故总时间复杂度 $O(n\sqrt n)$。