CF2185G Mixing MEXes

给定 $n$ 个数组 $a_1, a_2, \ldots, a_n$。 对这些数组恰好执行一次如下操作： - 在 $a_1, a_2, \ldots, a_n$ 中任选一个数组。假设选择了 $a_i$（$1 \leq i \leq n$）。 - 在该数组 $a_i$ 内任选一个元素。假设选择了 $a_i$ 的第 $j$ 个元素，记为 $a_{i,j}$（$1 \leq j \leq |a_i|$，其中 $|a_i|$ 表示数组 $a_i$ 的长度）。 - 在其它数组中选一个（不能是 $a_i$ 本身）。假设选择了 $a_k$（$1 \leq k \leq n, k \neq i$）。 - 将 $a_{i,j}$ 加到数组 $a_k$ 的末尾，并且从 $a_i$ 中移除 $a_{i,j}$。 - 本次操作 $(i, j, k)$ 的价值定义为操作执行后所有数组的 $\operatorname{MEX}$ 之和。更正式一点，操作后的价值为 $\sum_{i=1}^{n} \operatorname{MEX}(a_i)$。 请计算所有可能的不同独立操作的价值之和。 两个操作不同，当且仅当有序三元组 $(i, j, k)$ 不同。 $\operatorname{MEX}(a)$ 定义为不在数组中的最小非负整数。例如，$\operatorname{MEX}([1, 2, 0, 5]) = 3$，而 $\operatorname{MEX}([1, 2, 4, 9]) = 0$。

输入的第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例数量。 每个测试用例的第一行包含一个整数 $n$（$2 \leq n \leq 2 \times 10^5$），表示数组的个数。 接下来 $n$ 行，每行以 $l_i$（$1 \leq l_i \leq 10^5$）开头，表示第 $i$ 个数组的长度，后跟 $l_i$ 个整数 $a_1, a_2, \ldots, a_{l_i}$（$0 \leq a_{i_j} \leq 10^6$），构成数组 $a_i$。 保证所有测试用例中 $l_i$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出所有可能不同操作的价值之和。

对于第一个测试用例，总共有 3 个不同的操作： - $i = 1, j = 1, k = 2$：数组变为 $[]$ 和 $[0, 1, 2]$，$\operatorname{mex}$ 分别为 $0$ 和 $3$，因此操作价值为 $3$。 - $i = 2, j = 1, k = 1$：数组变为 $[0, 1]$ 和 $[2]$，$\operatorname{mex}$ 分别为 $2$ 和 $0$，因此操作价值为 $2$。 - $i = 2, j = 2, k = 1$：数组变为 $[0, 2]$ 和 $[1]$，$\operatorname{mex}$ 分别为 $1$ 和 $0$，因此操作价值为 $1$。 对于第二个测试用例，由于每个数组都不包含 $0$，因此所有操作的价值均为 $0$。 由 ChatGPT 5 翻译