题目背景

What age is it that you are still solving traditional path query problems?

题目描述

After reading the paper Distributed Exact Shortest Paths in Sublinear Time, you have learned how to solve the distributed single-source shortest paths problem in $\mathcal{O}(D^{1/3} \cdot (n \log n)^{2/3})$. To give your knowledge good practice, Little Cyan Fish prepared the following practice task for you.

Little Cyan Fish has a graph consisting of $n$ vertices and $m$ bidirectional edges. The vertices are numbered from $1$ to $n$. The $i$-th edge connects vertex $u_i$ to vertex $v_i$ and is assigned a weight $w_i$.

For any path in the graph between two vertices $u$ and $v$, let's define the value of the path as the bitwise AND of the weights of all the edges in the path.

As a fan of high-value paths, Little Cyan Fish has set a constant threshold $V$. Little Cyan Fish loves a path if and only if its value is at least $V$.

Little Cyan Fish will now ask you $q$ queries, where the $i$-th query can be represented as a pair of integers $(u_i, v_i)$. For each query, your task is to determine if there exists a path from vertex $u_i$ to vertex $v_i$ that Little Cyan Fish would love it.

输入格式

There is only one test case in each test file.

The first line contains four integers $n$, $m$, $q$ and $V$ ($1 \le n \le 10^5$, $0 \le m \le 5 \times 10^5$, $1 \leq q \leq 5 \times 10^5$, $0 \leq V < 2^{60}$) indicating the number of vertices, the number of edges, the number of queries and the constant threshold.

For the following $m$ lines, the $i$-th line contains three integers $u_i$, $v_i$ and $w_i$ ($1 \le u_i,v_i \le n$, $u_i \ne v_i$, $0 \leq w_i < 2^{60}$), indicating a bidirectional edge between vertex $u_i$ and vertex $v_i$ with the weight $w_i$. There might be multiple edges connecting the same pair of vertices.

For the following $q$ lines, the $i$-th line contains two integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n$, $u_i \ne v_i$), indicating a query.

输出格式

For each query output one line. If there exists a path whose value is at least $V$ between vertex $u_i$ and $v_i$ output Yes, otherwise output No.

题目大意

【题目背景】

都什么年代了还在做传统路径查询问题？

【题目描述】

在阅读《Distributed Exact Shortest Paths in Sublinear Time》这篇论文后，您学会了如何在 $\mathcal{O}(D^{1/3} \cdot (n \log n)^{2/3})$ 的复杂度内解决分布式单源最短路问题。为了测试您是否真的学有所成，小青鱼为您准备了如下问题。

小青鱼有一张包含 $n$ 个节点与 $m$ 条无向边的图，节点编号从 $1$ 到 $n$。第 $i$ 条边连接节点 $u_i$ 和 $v_i$，边权为 $w_i$。

对于任意一条连接节点 $u$ 和 $v$ 的路径，定义路径的价值为路径上所有边的边权进行按位与（bitwise AND）计算的结果。

小青鱼很喜欢高价值的路径，因此他设定了一个固定的阈值 $V$。称小青鱼喜爱一条路径，当且仅当这条路径的价值至少为 $V$。

接下来，小青鱼将会提出 $q$ 次询问，第 $i$ 次询问可以用一对整数 $(u_i, v_i)$ 表示。对于每次询问，您需要判断节点 $u_i$ 到 $v_i$ 是否存在一条小青鱼喜爱的路径。

【输入格式】

每个测试文件仅有一组测试数据。

第一行输入四个整数 $n$，$m$，$q$ 和 $V$（$1 \le n \le 10^5$，$0 \le m \le 5 \times 10^5$，$1 \leq q \leq 5 \times 10^5$，$0 \leq V < 2^{60}$）表示图中的节点数以及边数，小青鱼的询问数以及固定阈值。

对于接下来 $m$ 行，第 $i$ 行输入三个整数 $u_i$，$v_i$ 和 $w_i$（$1 \le u_i,v_i \le n$，$u_i \ne v_i$，$0 \leq w_i < 2^{60}$）表示一条连接节点 $u_i$ 和 $v_i$ 的无向边，边权为 $w_i$。两个节点之间可能存在多条边。

对于接下来 $q$ 行，第 $i$ 行输入两个整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$，$u_i \ne v_i$）表示一次询问。

【输出格式】

每次询问输出一行。若节点 $u_i$ 和 $v_i$ 之间存在一条价值至少为 $V$ 的路径输出 Yes，否则输出 No。

【样例解释】

接下来我们用 $\&$ 表示按位与计算。

第一组样例数据解释如下。

• 对于第一次询问，一条合法的路径为 $1 \to 3 \to 4 \to 5 \to 6$，其价值为 $7 \,\&\, 14 \,\&\, 7 \,\&\, 6 = 6 \ge 5$。
• 对于第三次询问，一条合法的路径为 $7 \to 3 \to 4 \to 5 \to 6$，其价值为 $15 \,\&\, 14 \,\&\, 7 \,\&\, 6 = 6 \ge 5$。
• 对于第四次询问，因为节点 $1$ 与 $8$ 之间不存在任何路径，因此答案为 No。

对于第二组样例数据仅有的一次询问，可以考虑由第 $2$ 和第 $4$ 条边组成的路径，其价值为 $5 \,\&\, 6 = 4 \ge 4$。

9 8 4 5
1 2 8
1 3 7
2 4 1
3 4 14
2 5 9
4 5 7
5 6 6
3 7 15
1 6
2 7
7 6
1 8

Yes
No
Yes
No

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

Yes

提示

We now use $\&$ to represent the bitwise AND operation.

The first sample test case is shown as follows.

• For the first query, a valid path is $1 \to 3 \to 4 \to 5 \to 6$, whose value is $7 \,\&\, 14 \,\&\, 7 \,\&\, 6 = 6 \ge 5$.
• For the third query, a valid path is $7 \to 3 \to 4 \to 5 \to 6$, whose value is $15 \,\&\, 14 \,\&\, 7 \,\&\, 6 = 6 \ge 5$.
• For the fourth query, as there is no path between vertex $1$ and $8$, the answer is No.

For the only query of the second sample test case, we can consider the path consisting of the $2$-nd and the $4$-th edge. Its value is $5 \,\&\, 6 = 4 \ge 4$.