AT_abc451_g [ABC451G] Minimum XOR Walk

你有一个简单连通无向图 $G$，有 $N$ 个点和 $M$ 条边。边从 $1$ 到 $M$ 编号，点从 $1$ 到 $N$ 编号。第 $i$ 条边连接点 $U_i$ 和 $V_i$ 且有边权 $W_i$。 一条途径的权值是走过的所有边的边权异或和。如果一条边被走过多次，那么这条边的权值也要被异或多次。 你有一个非负整数 $K$。找到有多少对 $(x,y)(1 \le x < y \le N)$ 满足从 $x$ 到 $y$ 的所有途径中，权值最小的路径权值不超过 $K$。 有 $T$ 次询问，你需要解决每一个。 **途径**：途径是连接一连串顶点的边的序列。形式化地说，一条有限途径 $w$ 是一个边的序列 $e_1, e_2, \ldots, e_k$，使得存在一个顶点序列 $v_0, v_1, \ldots, v_k$ 满足 $e_i = (v_{i-1}, v_i)$，其中 $i \in [1, k]$。这样的途径可以简写为 $v_0 \to v_1 \to v_2 \to \cdots \to v_k$。 **异或**：非负整数 $A$ 和 $B$ 的按位异或运算 $A \oplus B$ 定义如下： - 在 $A \oplus B$ 的二进制表示中，$2^k$（$k \geq 0$）位上的数字为 $1$，当且仅当 $A$ 与 $B$ 的二进制表示中 $2^k$ 位上的数字恰好有一个为 $1$；否则该位为 $0$。 例如，$3 \oplus 5 = 6$（二进制下：$011 \oplus 101 = 110$）。 一般地，$k$ 个非负整数 $p_1, p_2, p_3, \dots, p_k$ 的按位异或定义为 $(\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k)$，并且可以证明其结果与 $p_1, p_2, p_3, \dots, p_k$ 的顺序无关。

第一行一个正整数 $T$，代表询问次数。 接下来每次询问，第一行三个整数 $N,M,K$，意义如题目所述。接下来 $M$ 行，每行三个整数 $U_i,V_i,W_i$，意义如题目所述。

输出 $T$ 行，第 $i$ 行是第 $i$ 次询问的答案。

### 样例解释 1 在第一个测试用例中，例如，依次经过顶点 $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$。 ### 约束 - $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 < 2^{30}$ - $1 \leq U_i < V_i \leq N$ - $0 \leq W_i < 2^{30}$ - 给定的图是简单连通无向图。 - 所有输入值均为整数。 - 单个输入中所有测试用例的 $N$ 之和不超过 $2 \times 10^5$。 - 单个输入中所有测试用例的 $M$ 之和不超过 $2 \times 10^5$。