分数: 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 否则。
约束
- 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).