#P18649. XOR Reachable
XOR Reachable
XOR Reachable
题目描述
给定整数 和一张有 个顶点、 条边的无向图。顶点编号为 ,边编号为 。第 条边连接顶点 和 ,非负整数边权为 。
图中可能有重边,不含自环。输入中的 仅将每条无向边的两个端点按大小排列。
有 次询问,第 次询问给出一个整数 。请计算满足下列条件的整数对 的数量:
- 。
- 可以仅使用满足 的边 ,从顶点 到达顶点 。
其中 表示按位异或运算。
输入格式
N M K
A_1 B_1 C_1
A_2 B_2 C_2
...
A_M B_M C_M
Q
D_1
D_2
...
D_Q
输入仅包含一组数据,所有数均为整数。
输出格式
输出 行。第 行输出一个整数,表示第 次询问的答案。
数据范围
- 。
- 。
- 。
- 。
- 。
- 。
- 。
样例输入 1
4 5 5
1 2 17
1 3 4
2 3 20
2 4 3
3 4 5
4
0
7
16
167
样例输出 1
2
6
3
0
样例输入 2
9 13 488888932
2 7 771479959
3 8 783850182
5 7 430673756
6 8 350738034
4 9 400768807
2 3 83653266
1 2 829786563
5 8 357613791
7 9 579696618
3 7 423191200
3 5 867380255
1 9 907715012
6 9 1033650694
8
498260055
144262908
117665696
848664012
983408133
32610599
478007408
134182829
样例输出 2
16
7
5
13
13
16
16
5