All Tracks>Problem
XOR paths
★★★★★

3.8

12 votes
Linear Algebra, Fast Fourier transform, Fourier Transformations, Walsh-Hadarm transform, Medium-Hard, Modular exponentiation, Mathematics
Problem

You are given a weighted tree with \(N\) vertices. You can denote the value of path of vertices \(V\) and \(U\) as XOR of weights of all edges on path from \(V\) to \(U\). Your task is to print the number of four vertices \((A, B, C, D)\) such that the value of path of vertices \(A\) and \(B\) differs from the value of path of vertices \(C\) and \(D\) in not more than one bit. 

Input format

  • First line: \(N\) \((1 \leq N \leq 10^5)\)
  • Each of the next \(N-1\) lines: Three space-separated integers \(X, Y, Z\) \((1 \leq X, Y \leq N, \, 0 \leq Z \leq 10^5)\) that represents an edge between vertices \(X\) and \(Y\) with weight \(Z\)

Output format

Print one integer that represents the answer for the problem modulo \(1000000007\) \((10^9+7)\).

Test data

  • In 12.5% of tests: \((1 \leq N \leq 100)\)
  • In 37.5% of tests: \((1 \leq N \leq 1000)\)
  • In 50.0% of tests: \((1 \leq N \leq 100000)\)
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

There are \(61\) fourth of vertices:

  1. (1, 1, 1, 1)
  2. (1, 1, 1, 2)
  3. (1, 1, 2, 1)
  4. (1, 1, 2, 2)
  5. (1, 1, 2, 3)
  6. (1, 1, 3, 2)
  7. (1, 1, 3, 3)
  8. (1, 2, 1, 1)
  9. (1, 2, 1, 2)
  10. (1, 2, 1, 3)
  11. (1, 2, 2, 1)
  12. (1, 2, 2, 2)
  13. (1, 2, 3, 1)
  14. (1, 2, 3, 3)
  15. (1, 3, 1, 2)
  16. (1, 3, 1, 3)
  17. (1, 3, 2, 1)
  18. (1, 3, 2, 3)
  19. (1, 3, 3, 1)
  20. (1, 3, 3, 2)
  21. (2, 1, 1, 1)
  22. (2, 1, 1, 2)
  23. (2, 1, 1, 3)
  24. (2, 1, 2, 1)
  25. (2, 1, 2, 2)
  26. (2, 1, 3, 1)
  27. (2, 1, 3, 3)
  28. (2, 2, 1, 1)
  29. (2, 2, 1, 2)
  30. (2, 2, 2, 1)
  31. (2, 2, 2, 2)
  32. (2, 2, 2, 3)
  33. (2, 2, 3, 2)
  34. (2, 2, 3, 3)
  35. (2, 3, 1, 1)
  36. (2, 3, 1, 3)
  37. (2, 3, 2, 2)
  38. (2, 3, 2, 3)
  39. (2, 3, 3, 1)
  40. (2, 3, 3, 2)
  41. (2, 3, 3, 3)
  42. (3, 1, 1, 2)
  43. (3, 1, 1, 3)
  44. (3, 1, 2, 1)
  45. (3, 1, 2, 3)
  46. (3, 1, 3, 1)
  47. (3, 1, 3, 2)
  48. (3, 2, 1, 1)
  49. (3, 2, 1, 3)
  50. (3, 2, 2, 2)
  51. (3, 2, 2, 3)
  52. (3, 2, 3, 1)
  53. (3, 2, 3, 2)
  54. (3, 2, 3, 3)
  55. (3, 3, 1, 1)
  56. (3, 3, 1, 2)
  57. (3, 3, 2, 1)
  58. (3, 3, 2, 2)
  59. (3, 3, 2, 3)
  60. (3, 3, 3, 2)
  61. (3, 3, 3, 3)
Editor Image

?