← 返回题目列表

Codeforces · 2129/E

E. 诱导子图查询

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

给您一个未加权、无向图 $$$G$$$,其中包含 $$$n$$$ 节点和 $$$m$$$ 边。图 $$$G$$$ 不包含自环或多重边。

我们将$$$G$$$的节点集表示为$$$V$$$。对于任意节点子集 $$$V' \subseteq V$$$,相应的导出子图用 $$$G[V']$$$ 表示,定义如下:

  • $$$G[V']$$$ 是节点集为 $$$V'$$$ 的图,其边集由 $$$G$$$ 中的所有边组成,且两个端点都在 $$$V'$$$ 中。

您的任务是回答 $$$q$$$ 查询。每个查询提供三个整数$$$l$$$、$$$r$$$ 和$$$k$$$。表示$$$V'=\{l,l+1,\ldots,r\}$$$,你需要找到$$$f(l,G[V'])$$$, $$$f(l+1,G[V'])$$$, $$$\ldots$$$ , $$$f(r,G[V'])$$$中的第$$$k$$$个最小值(即按升序排列的第 $$$k$$$ 个值;重复的值会被计算多次)。

这里,$$$f(u,G[V'])=\bigoplus_{(u,v)\in G[V']}v$$$。换句话说,它是图$$$G[V']$$$中节点$$$u$$$的所有相邻节点的标签的按位异或值。

您可能需要阅读注释以更好地理解。

输入

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

每个测试用例都以两个整数 $$$n$$$ 和 $$$m$$$ 开头($$$2 \leq n \leq 1.5 \cdot 10^5$$$, $$$1 \leq m \leq 1.5 \cdot 10^5$$$)——分别是节点和边的数量。

接下来的 $$$m$$$ 行每行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$),表示节点 $$$u_i$$$ 和 $$$v_i$$$ 之间的无向边。

下一行包含一个整数 $$$q$$$ ($$$1 \leq q \leq 1.5 \cdot 10^5$$$) — 查询数。

接下来的 $$$q$$$ 行包含三个整数 $$$l$$$、$$$r$$$ 和 $$$k$$$ ($$$1 \leq l \leq r \leq n$$$, $$$1 \le k \le r-l+1$$$),定义有关导出子图的查询$$$G[\{l,\ldots,r\}]$$$。

保证图不包含自环或重边。

保证所有测试用例的 $$$n$$$、$$$m$$$ 和 $$$q$$$ 之和分别不超过 $$$1.5 \cdot 10^5$$$。

输出

对于每个测试用例,输出 $$$q$$$ 整数,表示每个查询的答案。

示例

输入
复制

2
4 5
1 3
1 4
2 3
2 4
3 4
3
1 2 2
1 3 1
2 4 3
2 1
2 1
3
1 1 1
2 2 1
1 2 2

输出
复制

0
3
7
0
0
2

注意

在第一个测试用例中,输入图 $$$G$$$ 如下图所示。

给定的图表$$$G$$$。

在第一个查询中,导出子图 $$$G[\{1,2\}]$$$ 如下图所示。我们可以看到节点$$$1$$$和$$$2$$$没有相邻节点。因此,$$$f(1,G[\{1,2\}])=f(2,G[\{1,2\}])=0$$$。 $$$2$$$第一个最小值是$$$0$$$。

$$$G[\{1,2\}]$$$。

在第二个查询中,导出子图 $$$G[\{1,2,3\}]$$$ 如下图所示。我们可以看到 $$$f(1,G[\{1,2,3\}])=3$$$,$$$f(2,G[\{1,2,3\}])=3$$$,$$$f(3,G[\{1,2,3\}])=1 \oplus 2=3$$$。 $$$1$$$-st 最小值是 $$$3$$$。

$$$G[\{1,2,3\}]$$$。

在第三个查询中,导出子图 $$$G[\{2,3,4\}]$$$ 如下图所示。我们可以看到 $$$f(2,G[\{2,3,4\}])=3 \oplus 4=7$$$、$$$f(3,G[\{2,3,4\}])=2 \oplus 4=6$$$ 和 $$$f(4,G[\{2,3,4\}])=2 \oplus 3=1$$$。 $$$3$$$-rd 最小值是 $$$7$$$。

$$$G[\{2,3,4\}]$$$。