Xor Distances

题目描述

我们有一棵带权树，包含 $N$ 个顶点。第 $i$ 条边双向连接顶点 $u_i$ 和顶点 $v_i$，并且权重为 $w_i$。 对于一对顶点 $(x,y)$，我们定义 $\text{dist}(x,y)$ 如下：

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

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

输入格式

输入从标准输入给出，格式如下： $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

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

提示

$2 \leq N \leq 2 \times 10^5$ $1 \leq u_i \lt v_i \leq N$ $0 \leq w_i \lt 2^{60}$ 给定的图是一棵树。 输入中的所有数值均为整数。我们有 $\text{dist}(1,2)=1,$ $\text{dist}(1,3)=3,$ 以及 $\text{dist}(2,3)=2$，它们的和为 $6$。
将和对 $(10^9+7)$ 取模后输出。

标签: AtCoder|abc201E

来源

AtCoder|abc201E