All Tracks Problem

Peculiar Paths



It is vacation time and the citizens of virtualBit are visiting their relatives. There are N cities in virtualBit. There are some roads connecting these cities in such a way that there is one and only one unique path between any pair of these cities. Each city sells only one type of gift with a fixed price Vi.

There are Q citizens who wish to visit their relatives. The ith citizen stays in city Ai and wants to visit his relative who lives in city Bi. They want to purchase some gifts for the children of their relatives. These gifts should be bought only from the cities that lie on the path from Ai to Bi (including the starting and ending points).

The children are very picky by nature. They love prime numbers and hence will only accept those gifts, whose cost is a prime number. Also, the children will only accept gifts that cost atleast Li . But they also understand the financial constraints of their relatives and hence will not accept any gift that costs more than Ri.

Each citizen wants to know the number of cities from which he can buy gifts for the children of his relative. Please help him in finding the answer.


The first line of the input contains two numbers N and Q, the number of cities and number of citizens respectively.

The next line contains N numbers. The ith number is the cost of gift being sold at city i.

The next N-1 lines contain two integers X and Y indicating that there is a bidirectional road between cities X and Y.

Each of the next Q lines contain a query of the form: A B L R.


For ith query, print the number of cities from which the ith citizen can buy gifts while obeying the constraints on the cost of gifts.




1<=X, Y<=N

1<=A, B<=N

1<=L, R<=106

8 2
105 2 9 3 8 5 7 10
1 2        
1 3
1 4
3 5
3 6
3 7
4 8
2 5 1 2
7 8 2 5
Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems


This Problem was Asked in

Initializing Code Editor...
View All Notifications