异或距离

题目描述

给定一棵有 $N$ 个顶点的带权树。第 $i$ 条边双向连接顶点 $u_i$ 和顶点 $v_i$，权重为 $w_i$。

对于顶点对 $(x,y)$，定义 $\text{dist}(x,y)$ 如下：

从 $x$ 到 $y$ 的最短路径上所有边的权重的异或值。

求所有满足 $1 \le i \lt j \le N$ 的顶点对 $(i,j)$ 的 $\text{dist}(i,j)$ 之和，并输出该和模 $(10^9+7)$ 的结果。

什么是异或？

整数 $A$ 与 $B$ 的按位异或 $A\ \mathrm{XOR}\ B$ 定义如下：

把 $A\ \mathrm{XOR}\ B$ 写成二进制时，第 $2^k$ 位（$k \geq 0$）上的数字为 1，当且仅当 $A$ 和 $B$ 中恰好有一个在该位上为 1；否则为 0。

例如，$3\ \mathrm{XOR}\ 5 = 6$（二进制：$011\ \mathrm{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)$ 的结果。

样例

3
1 2 1
1 3 3

6

我们有 $\text{dist}(1,2)=1$、$\text{dist}(1,3)=3$、$\text{dist}(2,3)=2$，总和为 6。

5
3 5 2
2 3 2
1 5 1
4 5 13

62

10
5 7 459221860242673109
6 8 248001948488076933
3 5 371922579800289138
2 5 773108338386747788
6 10 181747352791505823
1 3 803225386673329326
7 8 139939802736535485
9 10 657980865814127926
2 4 146378247587539124

241240228

输出总和模 $(10^9+7)$ 的结果。

数据范围

• $2 \le N \le 2 \times 10^5$
• $1 \le u_i \lt v_i \le N$
• $0 \le w_i \lt 2^{60}$
• 给定的图是一棵树
• 输入均为整数