5333: Tree Xor

Bob has a tree with n nodes and the weight of i-th node is w_i.
But Bob forgot w_1...n, he only remembers w_i is an integer in [l_i,r_i] and w_u xor w_v for each edge (u,v) in the tree.
Now Bob wants to know the number of possible values of w_1...n.
XOR means bitwise exclusive OR.

The first line has one integers n.
Then there are n lines, the i-th line has two integers l_i,r_i.
Then there are n−1 lines, each line has three integers u,v,w_u xor w_v denote the infomation for each edge.
1≤n≤10⁵
0≤l_i≤r_i<2³⁰
0≤w_u xor w_v<2³⁰

4
0 7
1 6
2 5
3 4
1 2 0
1 3 7
2 4 6

2