CF2239F Colorful Works

Gold14526 是一名画家。他可以使用 $n$ 种颜色进行绘画，这些颜色的编号分别为 $1, 2, \ldots, n$。第 $i$ 种颜色具有一个约束区间 $[l_i, r_i]$。 一个作品被定义为一棵有根树 $T=(V,E)$，并且每条边都被涂上了（$n$ 种颜色中的某一种）。如果以下条件被满足，这个作品就被称为“彩色的”： - 对于任意三个节点 $u, v, w \in V$，如果边 $(u,v)$ 和 $(v,w)$ 都存在，那么这两条边必须拥有不同的颜色。 - 对于所有颜色 $i \in [1,n]$，设 $d(u,i)$ 表示从节点 $u$ 到根节点的简单路径上颜色为 $i$ 的边的数量。那么 $\max_{u \in V} d(u,i) \in [l_i, r_i]$。 如果两棵作品 $T=(V,E)$ 和 $T'=(V',E')$ 满足下列两条条件，则称它们是同构的： - $|V| = |V'|$； - 存在一个双射 $f:V \to V'$，使得： - 设 $r$ 为 $T$ 的根，$r'$ 为 $T'$ 的根，则 $f(r) = r'$； - 对任意 $(u,v) \in E$，有 $(f(u),f(v)) \in E'$，并且边 $(u,v)$ 与 $(f(u),f(v))$ 的颜色相同。 Gold14526 想知道：他最多能选择多少棵相互之间不同构的彩色作品？请输出答案对 $\mathbf{2}$ 取模。

每组测试数据包含多组测试用例。第一行包含测试用例数量 $t$ （$1 \le t \le 10^4$）。接下来的描述为各个测试用例的内容。 每个测试用例的第一行为一个整数 $n$（$1\le n\le 2\cdot 10^6$），表示颜色的数量。 接下来的 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$0\le l_i\le r_i\le 2\cdot 10^5$，并且 $r_i \ge 1$），表示第 $i$ 种颜色的约束区间。 保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^6$。 设 $m=\max_{i=1}^n r_i$。保证所有测试用例中 $m$ 的总和不超过 $2\cdot 10^5$。

对于每个测试用例，输出 $0$ 或 $1$，表示最多可以选取的作品数量对 $2$ 取模的结果。

在第一个测试用例中，两种颜色的约束区间均为 $[0, 1]$。这意味着从根到任意节点的简单路径上，每种颜色最多只能出现 $1$ 次。满足条件、互不同构的树一共 $9$ 种： - $1$ 个节点的树：仅有根节点。 - $2$ 个节点的树：根节点通过颜色 $1$ 的边连接一个子节点，或通过颜色 $2$ 的边连接一个子节点。（共 $2$ 种） - $3$ 个节点的树： - 根节点连接两个子节点，分别用颜色 $1$ 和 $2$； - 一条从根出发、边依次为颜色 $1$ 、$2$ 的长度为 $2$ 路径； - 一条从根出发、边依次为颜色 $2$ 、$1$ 的长度为 $2$ 路径。（共 $3$ 种） - $4$ 个节点的树： - 根通过颜色 $1$ 连接一个子节点，该子节点通过颜色 $2$ 连接下一个节点，根还通过颜色 $2$ 连接另一个子节点。 - 根通过颜色 $2$ 连接一个子节点，该子节点通过颜色 $1$ 连接下一个节点，根还通过颜色 $1$ 连接另一个子节点。（共 $2$ 种） - $5$ 个节点的树：根通过颜色 $1$、$2$ 各连接一个子节点，每个子节点再分别有一个与其颜色不同的子节点。（共 $1$ 种） 由于 $9\equiv 1 \pmod 2$，所以输出 $1$。 在第二个测试用例中，两种颜色的约束区间均为 $[1, 1]$。每个合法的树都要求从根到任意节点的路径上，每种颜色出现的次数都“恰好”为 $1$。因此，树必须同时包含至少一条颜色为 $1$ 的边和至少一条颜色为 $2$ 的边。满足的树一共 $6$ 种： - $3$ 个节点的树：根节点连接两个子节点，分别用颜色 $1$ 和 $2$；一条长度为 $2$ 的路径，依次为颜色 $1$ 、$2$ 或 $2$ 、$1$。（共 $3$ 种） - $4$ 个节点的树：同第一个样例分析的两种 $4$ 节点树。 - $5$ 个节点的树：同第一个样例分析的 $5$ 节点树。 由于 $6\equiv 0 \pmod 2$，输出 $0$。 由 ChatGPT 5 翻译