Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Many Paths, Many Costs

By shefin · Limits 1s, 1.0 GB

Alice and Bob are visiting Byteland. They are observing the map of this country. Surprisingly, the map of Byteland forms a tree. A tree is a connected graph without cycles. After finding this out, Alice has fixed the starting and ending city of her journey. But Bob is super confused and can’t fix his route.

After some thinking, Bob has come up with a scheme. Let’s say Alice’s starting city is uu and ending city is vv. Then Bob will choose two different cities aa and bb such that both aa and bb lie on the simple path between city uu and city vv. A simple path is the path that visits each city at most once. Soon Bob finds out that there are still many options. So, he is considering all possible options. For each option of choosing two different cities aa and bb, he calculates the cost of the simple path between cities aa and bb and appends it to the list KK. After appending the costs of all options, he sorts the list KK in ascending order. Please note that choosing cities a,ba, b and cities b,ab, a are considered as the same option.

Each edge of the tree has some weight. Bob defines the cost of a simple path as the bit-wise XOR of all the weights of the edges lying on that simple path.

Now, Bob wants to analyze the costs in [L,R][L, R] subarray of the list KK. He wants your help to analyze this task. You need to calculate the product of all the costs in [L,R][L, R] subarray of the list KK. As the answer can be very large, you need to print the answer modulo (109+7)(10^9 + 7). More formally, you need to print (i=LRKi)mod(109+7)\left( \prod\limits_{i=L}^{R} K_i \right) \mod (10^9+7).

The bitwise xor operation is represented with the "⊕" logic symbol, which is denoted as the "^" operator in C/C++, Java and Python.


The first line of the input will contain an integer T(1T104)T(1\leq T\leq 10^4), the number of the test cases.

In each of the test cases, the first line will contain two integers N,Q(2N105;1Q104)N, Q (2\leq N\leq 10^5; 1\leq Q\leq 10^4), the number of cities in Byteland, and the number of queries. Each of the next (N1)(N-1) lines will contain three integers U,V,W(1U,VN;UV;0<W103)U, V, W (1\leq U, V\leq N; U\neq V; 0< W\leq10^3) denoting there is an undirected edge of WW weight between city UU and city VV. Each of the next QQ lines will contain four integers u,v,L,Ru, v, L, R (1u,vN;uv;1LR)(1\leq u, v\leq N; u\neq v; 1\leq L\leq R), the starting and ending cities of Alice and the list KK’s range Bob will analyze.

It is guaranteed that the given edges form a tree and the LL, RR will produce a valid range.

The sum of NN over all test cases won’t exceed 10510^5 and the sum of QQ over all test cases won’t exceed 10410^4.


In each query, print (i=LRKi)mod(109+7)\left( \prod\limits_{i=L}^{R} K_i \right) \mod (10^9+7) in a line.


5 2
1 2 6
2 3 13
2 5 12
3 4 5
4 5 2 4
1 3 1 3


In the first query, the costs of the paths Bob will consider are:
Cost(2,3)=13,Cost(2,4)=8,Cost(2,5)=12,Cost(3,4)=5,Cost(3,5)=1,Cost(4,5)=4Cost(2, 3) = 13, Cost(2, 4) = 8, Cost(2,5)=12, Cost(3,4)=5, Cost(3,5)=1, Cost(4,5)=4.

So, the list KK will be: [1,4,5,8,12,13][1, 4, 5, 8, 12, 13].
The value of (i=24Ki)mod(109+7)\left( \prod\limits_{i=2}^{4} K_i \right) \mod (10^9+7) = (4×5×8)mod(109+7)(4\times 5\times 8) \mod (10^9+7) = 160160.



100% Solution Ratio

NirjhorEarliest, 1M ago

ShadowMeFastest, 0.6s

NirjhorLightest, 424 MB

serotoninShortest, 2586B


Login to submit


At first, let’s take any arbitrary node as the root of the tree. Let, p[u]=Cost(root,u)p[u] = Cost(r...

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.