分数: 600 点
问题陈述
给你一个简单的连通无向图 N 顶点和 M 边缘。 顶点已编号 1 通过 N 且边缘已编号 1 通过 M;边缘 i 是权重的无向边 W_i 连接顶点 U_i 和 V_i.
连接两个顶点的路径权重定义为路径中包含的边权重的总异或。 如果同一条边被遍历多次,则该边的权重将影响总异或次数。
给你一个非负整数 K。查找整数对的数量 (x, y) (1 \leq x \lt y \leq N) 使得连接顶点的步行的最小权重 x 和 y 最多是 K.
T 给出了测试用例;逐一解决。
什么是散步?
对于顶点 无向图中的 X 和 Y 在无向图中 G,一系列 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.
什么是异或?
非负整数的按位异或 A 和 B, A \oplus B定义如下。
- 处的数字 2^k (k \geq 0) 放置在二进制表示中 A \oplus B is 1 如果恰好是位于的数字之一 2^k 放置在二进制表示中 A 和 B is 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.
约束
- 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}
- 给定的图很简单且连通。
- 所有输入值均为整数。
- 总和 N 单个输入中的所有测试用例最多 2 \times 10^5.
- 总和 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 在第一行。