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≤N≤105)
  • Each of the next N−1 lines: Three space-separated integers X,Y,Z (1≤X,Y≤N,0≤Z≤105) 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 (109+7).

Test data

  • In 12.5% of tests: (1≤N≤100)
  • In 37.5% of tests: (1≤N≤1000)
  • In 50.0% of tests: (1≤N≤100000)
Sample Input
3
2 1 1
3 2 2
Sample Output
61
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)
Contributers:
Editor Image

?