题目描述
N 頂点の重み付き木があります。i 本目の辺は頂点 ui と頂点 vi を双方向に結んでいて、その重みは wi です。
頂点の組 (x,y) について、dist(x,y) を以下のように定めます。
- x から y への最短パスに含まれる辺全ての重みの XOR
1 ≤ i < j ≤ N を満たす全ての組 (i,j) について dist(i,j) を求め、その総和を (109+7) で割った余りを出力してください。
XOR とは 整数 a, b のビットごとの排他的論理和 a XOR b は、以下のように定義されます。
- a XOR b を二進表記した際の 2k (k ≥ 0) の位の数は、a, b を二進表記した際の 2k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
例えば、3 XOR 5 = 6 となります (二進表記すると: 011 XOR 101 = 110)。
输入格式
入力は以下の形式で標準入力から与えられる。
N u1 v1 w1 u2 v2 w2 ⋮ uN−1 vN−1 wN−1
输出格式
dist(i,j) の総和を (109+7) で割った余りを出力せよ。
题目大意
给定一棵带权无根树,定义 dis(i,j) 为 i 到 j 最短路径上边权的异或和。
求 1≤i<j≤n∑dis(i,j),对 109+7 取模。
提示
制約
- 2 ≤ N ≤ 2 × 105
- 1 ≤ ui < vi ≤ N
- 0 ≤ wi < 260
- 与えられるグラフは木
- 入力は全て整数
Sample Explanation 1
dist(1,2)=1, dist(1,3)=3, dist(2,3)=2 であり、これらの総和は 6 です。
Sample Explanation 3
(109+7) で割った余りを出力してください。