CF2185G.Mixing MEXes

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定 $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$ 。

输出格式

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

输入输出样例

输入#1

6
2
1 0
2 1 2
3
1 1
2 2 3
3 4 5 6
5
4 1 7 8 10
2 5 6
2 0 7
2 6 6
2 6 8
2
1 3
3 0 1 2
2
6 0 0 1 2 2 3
3 0 2 3
10
1 0
9 7 8 0 1 5 6 4 3 2
8 4 3 8 6 2 5 0 1
7 2 3 0 1 0 4 0
2 3 1
9 2 0 5 4 1 3 0 0 0
7 6 3 2 4 1 8 0
5 3 2 4 1 0
4 0 3 1 1
3 0 3 2

输出#1

说明/提示

对于第一个测试用例，总共有 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$ 。

首页