← 返回题目列表

Codeforces · 1659/E

E. AND-MEX 步行

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

有一个无向连通图,具有 $$$n$$$ 个顶点和 $$$m$$$ 加权边。从顶点 $$$u$$$ 到顶点 $$$v$$$ 的步行定义为一系列顶点 $$$p_1,p_2,\ldots,p_k$$$(不一定不同),从 $$$u$$$ 开始,以 $$$v$$$ 结束,这样 $$$p_i$$$ 和 $$$p_{i+1}$$$ 通过 $$$1 的边连接\leq i < k$$$。

我们将步行的长度定义如下:获取有序的边序列,并将每条边的权重写在数组中。现在,记下该数组的每个非空前缀的按位与。步行的长度是所有这些值的 MEX。

更正式地说,让我们有 $$$[w_1,w_2,\ldots,w_{k-1}]$$$,其中 $$$w_i$$$ 是 $$$p_i$$$ 和 $$$p_{i+1}$$$ 之间的边的权重。那么行走的长度由 $$$\mathrm{MEX}(\{w_1,\,w_1\& w_2,\,\ldots,\,w_1\& w_2\& \ldots\& w_{k-1}\})$$$ 给出,其中 $$$\&$$$ 表示按位 AND 运算。

现在您必须处理 u v 形式的 $$$q$$$ 查询。对于每个查询,找到从 $$$u$$$ 到 $$$v$$$ 的最小可能步行长度。

集合的 MEX(排除最小值)是不属于该集合的最小非负整数。例如:

- $$$\{2,1\}$$$ 的 MEX 是 $$$0$$$,因为 $$$0$$$ 不属于该集合。
- $$$\{3,1,0\}$$$ 的 MEX 是 $$$2$$$,因为 $$$0$$$ 和 $$$1$$$ 属于该集合,但 $$$2$$$ 不属于该集合。
- $$$\{0,3,1,2\}$$$ 的 MEX 是 $$$4$$$,因为 $$$0$$$、$$$1$$$、$$$2$$$ 和 $$$3$$$ 属于该集合,但 $$$4$$$ 不属于该集合。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \leq n \leq 10^5$$$; $$$n-1 \leq m \leq \min{\left(\frac{n(n-1)}{2},10^5\right)}$$$)。

接下来的 $$$m$$$ 行包含三个整数 $$$a$$$、$$$b$$$ 和 $$$w$$$ ($$$1 \leq a, b \leq n$$$, $$$a \neq b$$$; $$$0 \leq w < 2^{30}$$$) 表示顶点之间的无向边$$$a$$$ 和顶点 $$$b$$$,权重为 $$$w$$$。输入不会包含自循环或重复边,并且提供的图将被连接。

下一行包含一个整数 $$$q$$$ ($$$1 \leq q \leq 10^5$$$)。

接下来的 $$$q$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$),即每个查询的描述。

输出

对于每个查询,打印一行包含单个整数 - 查询的答案。

示例

输入 #1

6 7
1 2 1
2 3 3
3 1 5
4 5 2
5 6 4
6 4 6
3 4 1
3
1 5
1 2
5 3

输出 #1

2
0
1

输入 #2

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

输出 #2

0
0
2
0
0
2
1
0
1
1

注意

以下是第一示例的说明。

第一个示例中的图表。

以下是第一个查询的可能步骤:

$$$$$$1 \overset{5}{\rightarrow} 3 \overset{3}{\rightarrow} 2 \overset{1}{\rightarrow} 1 \overset{5}{\rightarrow} 3 \overset{1}{\rightarrow} 4 \overset{2}{\rightarrow} 5.$$$$$$

权重数组为 $$$w=[5,3,1,5,1,2]$$$。现在,如果我们对该数组的每个前缀进行按位与,我们就得到集合 $$$\{5,1,0\}$$$。该集合的 MEX 为 $$$2$$$。我们无法获得更短长度的步行(如声明中所定义)。