AT_ttpc2022_i.XOR Reachable

给定整数 $N, M, K$，以及一个包含 $N$ 个顶点、$M$ 条边的无向图。图中每个顶点编号为 $1$ 到 $N$，每条边编号为 $1$ 到 $M$。第 $i$ 条边 ($1 \le i \le M$) 连接顶点 $A_i$ 和顶点 $B_i$，且边上有一个非负整数 $C_i$。

接下来给出 $Q$ 个查询。对于第 $i$ 个查询（$1 \le i \le Q$），给定一个整数 $D_i$。请你求满足下列所有条件的整数对 $(u, v)$ 的个数：

• $1 \le u < v \le N$
• 只能通过满足 $(C_j \oplus D_i) < K$ 的边 $j$，从顶点 $u$ 移动到顶点 $v$

这里 $\oplus$ 表示按位异或运算。

按位异或运算 $X \oplus Y$ 的定义如下：将 $X$ 和 $Y$ 转换为二进制，对于每一个 $2^k$ 位（$0 \le k$），如果 $X$ 和 $Y$ 的该位不同则为 $1$，否则为 $0$。

例如，$3 \oplus 5 = 6$，因为二进制表示为 $011 \oplus 101 = 110$。

输入按以下格式由标准输入给出。

$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

• 在第 $1$ 个查询中，仅能通过边 $2,4$。
• 在第 $2$ 个查询中，仅能通过边 $2,4,5$。
• 在第 $3$ 个查询中，仅能通过边 $1,3$。
• 在第 $4$ 个查询中，无法通过任何边。

数据范围

• 所有输入均为整数。
• $2 \le N \le 10^{5}$
• $1 \le M \le 10^{5}$
• $0 \le K < 2^{30}$
• $1 \le A_i < B_i \le N$ ($1 \le i \le M$)
• $0 \le C_i < 2^{30}$ ($1 \le i \le M$)
• $1 \le Q \le 10^{5}$
• $0 \le D_i < 2^{30}$ ($1 \le i \le Q$)

由 ChatGPT 5 翻译