← 返回题目列表

AtCoder · abc201_e

E. 异或距离

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

我们有一棵加权树 N 顶点。的 i第一条边连接顶点 u_i 和顶点 v_i 双向且具有权重 w_i.

对于一对顶点 (x,y),让我们定义 \text{dist}(x,y) 如下:

  • 这 异或 最短路径中的边的权重 x to y.

查找 每对 \text{dist}(i,j) 对于每对 (i,j) 这样 1 \leq i \lt j \leq N,并打印这些值模的总和 (10^9+7).

什么是 \text{ XOR }?

按位 \mathrm{XOR} 整数 A 和 B, A\ \mathrm{XOR}\ B,定义如下:

  • 当 A\ \mathrm{XOR}\ B 以基数 2 书写,即 2^k的地点 (k \geq 0)是 1 如果恰好是以下之一 A 和 B is 1,和 0 否则。
例如,我们有 3\ \mathrm{XOR}\ 5 = 6 (以二为基数: 011\ \mathrm{XOR}\ 101 = 110).

约束

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq u_i \lt v_i \leq N
  • 0 \leq w_i \lt 2^{60}
  • 给定的图是一棵树。
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

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).


示例输入 1

3
1 2 1
1 3 3

示例输出 1

6

我们有 \text{dist}(1,2)=1, \text{dist}(1,3)=3, 和 \text{dist}(2,3)=2,总和 6.


示例输入 2

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

示例输出 2

62

示例输入 3

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

示例输出 3

241240228

打印模数之和 (10^9+7).