← 返回题目列表

Codeforces · 2239/F

F. 多彩作品

中文机器翻译题面 查看原题

Gold14526 是一名画家。他可以用$$$n$$$颜色进行绘画,编号为$$$1、2、\ldots、n$$$。颜色 $$$i$$$ 有一个约束区间 $$$[l_i, r_i]$$$。

作品被定义为 有根树 $$$T=(V,E)$$$,其中每条边都有颜色(使用 $$$n$$$ 颜色之一)。有一个作品叫做 多彩 如果满足以下条件:

  • 对于任意三个节点 $$$u, v, w \in V$$$,如果边 $$$(u,v)$$$ 和 $$$(v,w)$$$ 都存在,则它们必须具有不同的颜色。
  • 对于 [1,n]$$$ 中的所有颜色 $$$i,让 $$$d(u,i)$$$ 表示从节点 $$$u$$$ 到根的简单路径上颜色 $$$i$$$ 的边数。然后$$$\max_{u \in V} d(u,i) \in [l_i, r_i]$$$。

当且仅当满足以下两个条件时,两个作品 $$$T=(V,E)$$$ 和 $$$T'=(V',E')$$$ 被定义为同构:

  • $$$\lvert V\rvert = \lvert V'\rvert$$$;
  • 存在双射 $$$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想知道最大数量 多彩 他可以选择作品,使得这些作品是成对非同构的。输出答案 模数 $$$\bf2$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 2\cdot 10^6$$$) — 表示颜色数量。

以下 $$$n$$$ 行每行包含两个整数,其中第 $$$i$$$ $$$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$$$ 取模。

示例

输入
复制

4
2
0 1
0 1
2
1 1
1 1
3
0 2
0 1
0 1
3
1 2
1 1
1 1

输出
复制

1
0
1
1

注意

在第一个测试用例中,两种颜色的约束都是 $$$[0, 1]$$$。这意味着在从根开始的任何简单路径上,最多可以有 $$$1$$$ 颜色为 $$$1$$$ 的边缘,最多有 $$$1$$$ 颜色为 $$$2$$$ 的边缘。总共有 $$$9$$$ 有效的成对非同构树:

  • $$$1$$$ 树,具有 $$$1$$$ 节点:只是根。
  • 具有 $$$2$$$ 节点的 $$$2$$$ 树:根通过颜色 $$$1$$$ 的边或颜色 $$$2$$$ 的边连接到子节点。
  • $$$3$$$ 树,具有 $$$3$$$ 节点:
    • 根分别通过颜色 $$$1$$$ 和 $$$2$$$ 的边连接到两个子节点。
    • 从根开始的 $$$2$$$ 边的路径,颜色为 $$$1$$$,然后是 $$$2$$$。
    • 从根开始的 $$$2$$$ 边的路径,颜色为 $$$2$$$,然后是 $$$1$$$。
  • $$$2$$$ 树,具有 $$$4$$$ 节点:
    • 根有一个通过颜色 $$$1$$$ 的子级(还具有一个通过颜色 $$$2$$$ 的子级),还有另一个通过颜色 $$$2$$$ 的子级。
    • 根有一个通过颜色 $$$2$$$ 的子级(还具有通过颜色 $$$1$$$ 的子级),还有另一个通过颜色 $$$1$$$ 的子级。
  • $$$1$$$ 树,具有 $$$5$$$ 节点:根通过颜色 $$$1$$$ 和 $$$2$$$ 连接到两个子节点,并且每个子节点都有一个相反颜色的子节点。
由于 $$$9 \equiv 1 \pmod 2$$$,输出为 $$$1$$$。

在第二个测试用例中,两种颜色的约束均为 $$$[1, 1]$$$。每棵有效的树必须满足路径上每种颜色的最大计数恰好为 $$$1$$$。因此,树必须至少包含一条颜色为 $$$1$$$ 的边和至少一条颜色为 $$$2$$$ 的边。总共有 $$$6$$$ 有效树:

  • $$$3$$$ 树,具有 $$$3$$$ 节点:根通过颜色 $$$1$$$ 和 $$$2$$$ 连接到两个子节点;路径颜色为$$$1$$$,然后是$$$2$$$;路径颜色为$$$2$$$,然后是$$$1$$$。
  • 具有 $$$4$$$ 节点的 $$$2$$$ 树:与第一个测试用例中描述的两个 $$$4$$$ 节点树相同。
  • 具有 $$$5$$$ 节点的 $$$1$$$ 树:与第一个测试用例中描述的 $$$5$$$ 节点树相同。
由于 $$$6 \equiv 0 \pmod 2$$$,输出为 $$$0$$$。