• [E] XorAgain

  • 时间限制: 1000 ms 内存限制: 65535 K
  • 问题描述
  • There is a tree which contains n nodes, of course it has n - 1 edges, with weight.

    Now the problem is, finding the number of (a, b) that the exclusive-xor sum of the edges between a to b is zero. Note that (a, b) is equal to (b, a).

    Since the answer is very large, output it after module 1000, 000, 007.

  • 输入
  • Input starts with an integer T (T <= 10) denoting the number of test case.
    For each case, first line contains n (1 <= n <= 50000) denoting the number of node, next n - 1 lines following, each line contains three
    integers u, v and w (1 <= u, v <= n, 0 <= w <= 10000) which means there is an edge between u and v whose weight is w.
    You can assume that the input data is valid.
  • 输出
  • For each case, output the answer after module 1000, 000, 007.
  • 样例输入
  • 1
    5
    1 2 3
    1 3 3
    2 4 4
    3 5 4
  • 样例输出
  • 7
  • 提示
  • In the example, the seven pair nodes are (1, 1)、(2, 2) 、(3, 3)、 (4, 4) 、(5, 5)、 (2, 3) and (4, 5).
    
  • 来源
  • Alex@NBUT
  • 操作

显示春菜