← 返回题目列表

AtCoder · abc451_g

G. 最小异或行走

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

分数: 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 在第一行。