问题 E: 简单异或问题
内存限制：1024 MB
时间限制：3.000 S
评测方式：文本比较
命题人：
提交：4
解决：3
题目描述
有一颗有 $N$ 个结点的树，其中第 $i$ 条边连接着结点 $u_i$ 和 $v_i$ ，权值为 $w_i$ 。我们定义两个结点的距离 $dis(x,y)$ 为从 $x$ 到 $y$ 经过的路径上的所有边的权值的异或值。你需要求出所有 $1 \le i < j \le N$ 的$dis(i,j)$ 的总和。
输入
$N$
$u_1$ $v_1$ $w_1$
$u_2$ $v_2$ $w_2$
...
$u_{N-1}$ $v_{N-1}$ $w_{N-1}$
$2 \le N \le 2×10^5$
$1 \le u_i < v_i \le N$
$0 \le w_i < 2^{60}$
所有输入数据都是整数
$u_1$ $v_1$ $w_1$
$u_2$ $v_2$ $w_2$
...
$u_{N-1}$ $v_{N-1}$ $w_{N-1}$
$2 \le N \le 2×10^5$
$1 \le u_i < v_i \le N$
$0 \le w_i < 2^{60}$
所有输入数据都是整数
输出
所有 $dis(i,j)$ 的和对 $(10^9+7)$ 取模。
样例输入 复制
5
3 5 2
2 3 2
1 5 1
4 5 13
样例输出 复制
62