I - XOR Reachable Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

整数 N,M,K と N 頂点 M 辺の無向グラフが与えられます。グラフの頂点には 1 から N の番号が、辺には 1 から M の番号が付けられています。辺 i (1 ≤ i ≤ M) は頂点 A_i と頂点 B_i の間をつないでいて、辺上には非負整数 C_i が置かれています。

Q 個のクエリが与えられます。i 番目 (1 ≤ i ≤ Q) のクエリでは、整数 D_{i} が与えられるので、次の条件を全て満たす整数の組 (u,v) の個数を求めてください。

  • 1\le u\lt v\le N
  • (C_{j} \oplus D_{i})\lt K を満たすような辺 j のみを通って、頂点 u から頂点 v まで移動することが可能

ただし \oplus はビット単位 \text{XOR} 演算を表します。

ビット単位 \text{XOR} 演算とは 非負整数 X,Y のビット単位 \text{XOR} 演算、 X\oplus Y は以下のように定義されます。
  • X\oplus Y を二進表記したときの 2^{k}の位 (0\le k) は、 A,B を二進表記したときの 2^{k} の位が異なるなら 1 、そうでないなら 0 とする。
例えば、 3\oplus 5=6 となります。(二進表記すると 011\oplus 101=110 )

制約

  • 入力は全て整数
  • 2\le N\le 10^{5}
  • 1\le M\le 10^{5}
  • 0\le K\lt 2^{30}
  • 1\le A_{i} \lt B_{i}\le N (1 ≤ i ≤ M)
  • 0\le C_{i}\lt 2^{30} (1 ≤ i ≤ M)
  • 1\le Q\le 10^{5}
  • 0\le D_{i}\lt 2^{30} (1 ≤ i ≤ Q)

入力

入力は以下の形式で標準入力から与えられる。

N M K
A_{1} B_{1} C_{1}
A_{2} B_{2} C_{2}
\vdots
A_{M} B_{M} C_{M}
Q
D_{1}
D_{2}
\vdots
D_{Q}

出力

Q 行出力せよ。 i 行目 (1\le i\le Q) には i 番目のクエリの答えを出力せよ。

入力例 1

4 5 5
1 2 17
1 3 4
2 3 20
2 4 3
3 4 5
4
0
7
16
167

出力例 1

2
6
3
0
  • 1 番目のクエリでは、辺 2,4 のみを通ることができます。
  • 2 番目のクエリでは、辺 2,4,5 のみを通ることができます。
  • 3 番目のクエリでは、辺 1,3 のみを通ることができます。
  • 4 番目のクエリでは、どの辺も通ることができません。

入力例 2

9 13 488888932
2 7 771479959
3 8 783850182
5 7 430673756
6 8 350738034
4 9 400768807
2 3 83653266
1 2 829786563
5 8 357613791
7 9 579696618
3 7 423191200
3 5 867380255
1 9 907715012
6 9 1033650694
8
498260055
144262908
117665696
848664012
983408133
32610599
478007408
134182829

出力例 2

16
7
5
13
13
16
16
5