树上异或距离(Tree XOR Distance)

题目描述

有一棵含有 $n$ 个节点的树，节点编号为 $1,2,\cdots,n$。对于树上任意两个结点 $(u,v)$ 之间的距离定义为：从 $u$ 到 $v$ 的简单路径中所有边的权值的异或和，用 $f(u,v)$ 表示。显然，自己到自己的距离为 $0$，即 $f(u,u) = 0$。

现在，小 Z 想知道所有点对之间的距离的和，其中点对 $(u,v)$ 和 $(v,u)$ 算同一点对，只计算一次。形式化地表述为，要计算 $\sum_{i=1}^{n-1}\sum_{j=i+1}^n f(i,j)$。

由于结果可能太大，只需要输出对 $10^9+7$ 取模的结果。

输入格式

第一行输入一个正整数 $n$，表示树上节点的数量。

之后 $n-1$ 行，每行输入三个整数 $u,v,w$。表示一条点$u,v$ 间的双向边，其权值为 $w$。

输出格式

输出所有点对之间距离的和对 $10^9+7$ 取模的结果。

样例输入 #1

3
1 2 1
1 3 3

样例输出 #1

6

数据范围

【样例解释】

$f(1,2)=1,f(1,3)=3,f(2,3)=2$，因此答案为 $f(1,2)+f(1,3)+f(2,3)=1+3+2=6$。

【数据范围】

对于 $23\%$ 的数据，$2 \le n \le 10$；

对于 $33\%$ 的数据，$2 \le n \le 1000$；

对于 $100\%$ 的数据，$2 \le n \le 2 \times 10^5, 1 \le u, v \le n, 0 \le w \lt 2^{60}$，保证给出的图是一棵树。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1500。

测试点分布

出处：原题链接