AT_abc201_e [ABC201E] Xor Distances

有一棵包含 $N$ 个顶点的带权树。第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$，其权值为 $w_i$，且为无向边。 对于顶点对 $(x, y)$，定义 $\text{dist}(x, y)$ 为： - 从 $x$ 到 $y$ 的最短路径上所有边的权值的 **异或和**。 请计算所有满足 $1 \leq i < j \leq N$ 的顶点对 $(i, j)$ 的 $\text{dist}(i, j)$ 之和，并输出其对 $10^9+7$ 取模的结果。 **异或（XOR）** 的定义如下：对于整数 $a, b$，它们的按位异或 $a\ \text{XOR}\ b$ 定义为： - $a\ \text{XOR}\ b$ 的二进制表示中，第 $2^k$ 位（$k \geq 0$）为 $1$ 当且仅当 $a, b$ 的二进制表示中第 $2^k$ 位恰好有一个为 $1$，否则为 $0$。 例如，$3\ \text{XOR}\ 5 = 6$，因为二进制下 $011\ \text{XOR}\ 101 = 110$。

输入通过标准输入给出，格式如下： > $N$ > $u_1\ v_1\ w_1$ > $u_2\ v_2\ w_2$ > $\vdots$ > $u_{N-1}\ v_{N-1}\ w_{N-1}$

输出所有 $\text{dist}(i, j)$ 之和对 $10^9+7$ 取模的结果。

## 限制条件 - $2 \leq N \leq 2 \times 10^5$ - $1 \leq u_i < v_i \leq N$ - $0 \leq w_i < 2^{60}$ - 给定的图为一棵树 - 所有输入均为整数 ## 样例解释 1 $\text{dist}(1,2)=1,\ \text{dist}(1,3)=3,\ \text{dist}(2,3)=2$，它们的总和为 $6$。 ## 样例解释 3 请输出对 $10^9+7$ 取模的结果。 由 ChatGPT 4.1 翻译