/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 600 点
問題文
N 頂点 M 辺からなる単純連結無向グラフが与えられます。 頂点には 1 から N までの、辺には 1 から M までの番号がそれぞれ付けられており、辺 i は頂点 U_i と頂点 V_i を結ぶ重み W_i の無向辺です。
2 頂点を結ぶウォークの重みを、そのウォークが含む辺の重みの総 XOR とします。 ただし同じ辺を複数回通る場合、その辺の重みは通った回数分総 XOR に寄与するものとします。
非負整数 K が与えられます。整数の組 (x,y) (1\leq x\lt y\leq N) であって、頂点 x,y を結ぶウォークの重みの最小値が K 以下であるものの個数を求めてください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
ウォークとは
無向グラフ G 上の頂点 X,Y に対して、k 個の頂点と k-1 個の辺を交互に並べた列 (v_1,e_1,v_2,\dots,v_{k-1},e_{k-1},v_k) であって、v_1=X,v_k=Y かつ i=1,2,\dots,k-1 に対して e_i が v_i と v_{i+1} を結ぶ辺であるようなものを頂点 X から頂点 Y への ウォーク と呼びます。
XOR とは
非負整数 A, B のビット単位 XOR、A \oplus B は、以下のように定義されます。
- A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
例えば、3 \oplus 5 = 6 となります (二進表記すると: 011 \oplus 101 = 110)。 一般に k 個の非負整数 p_1, p_2, p_3, \dots, p_k のビット単位 XOR は (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) と定義され、これは p_1, p_2, p_3, \dots, p_k の順番によらないことが証明できます。
制約
- 1 \leq T \leq 10^5
- 2 \leq N \leq 2 \times 10^5
- N-1 \leq M \leq 2 \times 10^5
- 0 \leq K \lt 2^{30}
- 1 \leq U_i \lt V_i \leq N
- 0 \leq W_i \lt 2^{30}
- 与えられるグラフは単純かつ連結
- 入力はすべて整数
- 1 つの入力に含まれるテストケースについて、N の総和は 2 \times 10^5 以下
- 1 つの入力に含まれるテストケースについて、M の総和は 2 \times 10^5 以下
入力
入力は以下の形式で標準入力から与えられる。
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
ここで \mathrm{case}_i は i 番目のテストケースの入力を意味する。各テストケースは以下の形式で与えられる。
N M K U_1 V_1 W_1 U_2 V_2 W_2 \vdots U_M V_M W_M
出力
T 行出力せよ。i 行目には i 番目のテストケースについての答えを出力せよ。
入力例 1
3 4 4 2 3 4 3 1 3 4 1 2 3 2 3 2 5 7 14032 1 2 24681 3 5 25665 1 5 14154 2 3 23215 1 3 21259 4 5 24874 3 4 26495 8 10 109312507 6 8 793188457 7 8 501937135 1 2 954888411 2 7 109497327 1 6 791995625 2 6 665857693 1 3 101233808 1 7 114788578 4 6 953503358 5 8 624700613
出力例 1
4 9 22
一つ目のテストケースにおいて、例えば頂点 1,3,2,1,3 を順に通るウォークの重みは 4 \oplus 2 \oplus 3 \oplus 4 = 1 です。
相異なる頂点の組それぞれに対し、それらを結ぶウォークの重みの最小値は以下のようになることが示せます。
- 頂点 1 と頂点 2：最小値 3
- 頂点 1 と頂点 3：最小値 1
- 頂点 1 と頂点 4：最小値 2
- 頂点 2 と頂点 3：最小値 2
- 頂点 2 と頂点 4：最小値 1
- 頂点 3 と頂点 4：最小値 3
このうち最小値が K(=2) 以下の組は 4 組あります。したがって一行目には 4 を出力してください。
Score : 600 points
Problem Statement
You are given a simple connected undirected graph with N vertices and M edges. The vertices are numbered 1 through N and the edges are numbered 1 through M; edge i is an undirected edge of weight W_i connecting vertices U_i and V_i.
The weight of a walk connecting two vertices is defined as the total XOR of the weights of the edges contained in the walk. If the same edge is traversed multiple times, that edge's weight contributes to the total XOR that many times.
You are given a non-negative integer K. Find the number of pairs of integers (x, y) (1 \leq x \lt y \leq N) such that the minimum weight of a walk connecting vertices x and y is at most K.
T test cases are given; solve each one.
What is a walk?
For vertices X and Y in an undirected graph G, a sequence of k vertices and k-1 edges alternately arranged (v_1, e_1, v_2, \dots, v_{k-1}, e_{k-1}, v_k) such that v_1 = X, v_k = Y, and for each i = 1, 2, \dots, k-1, e_i is an edge connecting v_i and v_{i+1}, is called a walk from vertex X to vertex Y.
What is XOR?
The bitwise XOR of non-negative integers A and B, A \oplus B, is defined as follows.
- The digit at the 2^k (k \geq 0) place in the binary representation of A \oplus B is 1 if exactly one of the digits at the 2^k place in the binary representations of A and B is 1, and 0 otherwise.
For example, 3 \oplus 5 = 6 (in binary: 011 \oplus 101 = 110). In general, the bitwise XOR of k non-negative integers p_1, p_2, p_3, \dots, p_k is defined as (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k), and it can be proved that this does not depend on the order of p_1, p_2, p_3, \dots, p_k.
Constraints
- 1 \leq T \leq 10^5
- 2 \leq N \leq 2 \times 10^5
- N-1 \leq M \leq 2 \times 10^5
- 0 \leq K \lt 2^{30}
- 1 \leq U_i \lt V_i \leq N
- 0 \leq W_i \lt 2^{30}
- The given graph is simple and connected.
- All input values are integers.
- The sum of N over all test cases in a single input is at most 2 \times 10^5.
- The sum of M over all test cases in a single input is at most 2 \times 10^5.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
Here, \mathrm{case}_i denotes the input for the i-th test case. Each test case is given in the following format:
N M K U_1 V_1 W_1 U_2 V_2 W_2 \vdots U_M V_M W_M
Output
Output T lines. The i-th line should contain the answer for the i-th test case.
Sample Input 1
3 4 4 2 3 4 3 1 3 4 1 2 3 2 3 2 5 7 14032 1 2 24681 3 5 25665 1 5 14154 2 3 23215 1 3 21259 4 5 24874 3 4 26495 8 10 109312507 6 8 793188457 7 8 501937135 1 2 954888411 2 7 109497327 1 6 791995625 2 6 665857693 1 3 101233808 1 7 114788578 4 6 953503358 5 8 624700613
Sample Output 1
4 9 22
In the first test case, for example, the weight of the walk visiting vertices 1, 3, 2, 1, 3 in order is 4 \oplus 2 \oplus 3 \oplus 4 = 1.
It can be shown that the minimum weight of a walk connecting each pair of distinct vertices is as follows.
- Vertices 1 and 2: minimum 3
- Vertices 1 and 3: minimum 1
- Vertices 1 and 4: minimum 2
- Vertices 2 and 3: minimum 2
- Vertices 2 and 4: minimum 1
- Vertices 3 and 4: minimum 3
Among these, four pairs have a minimum value of at most K(=2). Thus, output 4 on the first line.