Tổng XOR Các Đường Đi

Buổi 46 — Centroid Decomposition
Points
30
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions

Đề bài

Cho một cây có trọng số gồm $N$ đỉnh đánh số từ $1$ đến $N$. Giá trị XOR của đường đi giữa hai đỉnh $u$ và $v$, ký hiệu $\text{xor_dist}(u, v)$, là phép XOR bit (bitwise XOR) của tất cả trọng số các cạnh trên đường đi đơn nối $u$ và $v$.

Hãy tính tổng $\text{xor_dist}(u, v)$ trên tất cả các cặp đỉnh $(u, v)$ với $1 \le u < v \le N$, lấy phần dư cho $10^9 + 7$.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên dương $N$ ($1 \le N \le 10^5$).
  • $N - 1$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u, v, w$ ($1 \le u, v \le N$, $0 \le w < 2^{20}$) biểu thị cạnh nối $u$ và $v$ có trọng số $w$.

Dữ liệu ra

  • In ra một số nguyên duy nhất là kết quả bài toán modulo $1000000007$.

Ví dụ

Dữ liệu vào
3
1 2 3
2 3 5
Dữ liệu ra
14

Giới hạn

  • $1 \le N \le 10^5$, $0 \le w < 2^{20}$.
Draft saved