← 返回题目列表

AtCoder · agc031_f

F. 在图上行走

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

分数: 2000 点

问题陈述

给你一个连通图 N 顶点和 M 边缘。顶点已编号 1 to N。的 i第一条边是长度为无向的边 C_i 连接顶点 A_i 和顶点 B_i.

另外,奇数 MOD 。

你将得到 Q 查询,应予以处理。查询采用以下形式:

  • 中给出 i第一个查询是 S_i, T_i 和 R_i。打印 YES 如果存在来自 Vertex 的路径 S_i 到顶点 T_i 其长度为 R_i 模数 MOD,并打印 NO 否则。一条路径可以多次遍历同一条边,或者使用刚刚使用过的边返回。

这里,在这个问题中,路径的长度是 不 其边本身的长度之和,但路径中使用的第一条边的长度乘以 1,第二条边乘以 2,第三条边乘以 4,等等。 (更正式地说,让 L_1,...,L_k 是所使用的边缘的长度,按此顺序。该路径的长度是 L_i \times 2^{i-1}.)

约束

  • 1 \leq N,M,Q \leq 50000
  • 3 \leq MOD \leq 10^{6}
  • MOD 是奇数。
  • 1 \leq A_i,B_i\leq N
  • 0 \leq C_i \leq MOD-1
  • 1 \leq S_i,T_i \leq N
  • 0 \leq R_i \leq MOD-1
  • 给定的图形已连接。 (它可能包含自环或多条边。)

输入

输入由标准输入按以下格式给出:

N M Q MOD
A_1 B_1 C_1
\vdots
A_M B_M C_M
S_1 T_1 R_1
\vdots
S_Q T_Q R_Q

输出

打印以下问题的答案 i- 第一个查询 i第行。


示例输入 1

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

示例输出 1

YES
NO

每个查询的答案如下:

  • 第一个查询:如果我们采取路径 1,2,3,其长度为 1 \times 2^0 + 2 \times 2^1 = 5,因此存在一条长度为 5 模数 2019。答案是 YES.
  • 第二个查询:无论我们从 Vertex 采取什么路径 1 到顶点 3,它的长度永远不会 4 模数 2019。答案是 NO.

示例输入 2

6 6 3 2019
1 2 4
2 3 4
3 4 4
4 5 4
5 6 4
6 1 4
2 6 1110
3 1 1111
4 5 1112

示例输出 2

YES
NO
NO

示例输入 3

1 2 3 25
1 1 1
1 1 2
1 1 13
1 1 6
1 1 14

示例输出 3

YES
YES
YES

示例输入 4

10 15 10 15
1 2 1
2 3 6
3 4 6
2 5 1
5 6 1
4 7 6
1 8 11
2 9 6
5 10 11
9 10 11
3 6 1
2 5 1
2 7 11
9 10 11
5 6 11
1 3 5
9 8 3
7 7 7
7 10 13
4 1 10
9 3 12
10 10 14
9 2 1
6 6 5
8 8 4

示例输出 4

YES
NO
NO
NO
NO
NO
NO
YES
YES
NO