Yes.

The observation is that all the parents of the nodes in a query has to be in the same path.

So find the parent of each node in a query and check if they are in the same path from root using LCA.

If you use cout and endl then you don't need an extra cout.flush() in C++.

Oh! Didn't notice. Thanks

For the 1st test case,

6 2 3

1 3

1 2 3

Can't we use the lamp with power 1 to light the whole street?

If we put it at position 0 , it will cover [0,1] . then at 2 covering [2,3] , then at 4 covering [4,5] and at 5 covering [5,6]

That way the total cost will be 4, which is cheaper.

The left index and the right index of your segment