题目内容

在一座数据中心，服务器通过光缆互相连接。整个网络包含 $n$ 台服务器和 $n-1$ 条光缆，保证网络连通且不存在环（即任意两台服务器之间有且仅有一条简单路径）。每条光缆都有一个固定的密钥，用一个非负整数表示。

对于任意两台服务器 $u$ 和 $v$，它们之间通信所使用的「路径密钥」定义为：从 $u$ 到 $v$ 的唯一简单路径上，所有光缆密钥的按位异或结果（用 $\oplus$ 表示异或运算）。特别地，当 $u = v$ 时，路径密钥为 $0$。

现在管理员会进行 $q$ 次查询，每次查询给定服务器 $u$ 和一个密钥值 $k$，请你计算有多少台服务器 $v$，使得 $u$ 到 $v$ 的路径密钥恰好等于 $k$。

约束：

• 服务器的数量 $n$ 和查询次数 $q$ 均满足 $1 \le n, q \le 10^5$。
• 光缆的密钥以及查询中的 $k$ 均为整数，且 $0 \le w, k < 2^{60}$。