AT_abc201_e.[ABC201E] Xor Distances

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一棵包含 $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$ 取模的结果。

输入输出样例

输入#1
```
3
1 2 1
1 3 3
```
输出#1
```
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

说明/提示

限制条件

$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 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页