Truck Delivery
Memory limit1024 MB
For each query (city C, weight W) on a tree, find the gcd of toll charges on edges from C to the root whose load-limit is at most W, or 0 if none apply.
- Level
Hard8 of 10
- Topics
- Tree, DFS, Number theory, Sorting
- Solved
- No attempts yet
Problem
Charles is a truck driver in the city of Googleland. Googleland is built in the form of a tree with N nodes, where each node represents a city and each edge represents a road between two cities. The cities are numbered 1 to N. The capital of Googleland is city 1. Each day Charles picks up a load of weight W in city C and wants to deliver it to city 1 along the simple path (which is unique) between the cities. Each road i has a toll which charges amount Ai if the weight of the load is greater than or equal to a load-limit Li.
Charles works for Q days, where each day Charles is given the starting city C and the weight of the load W. For each day, find the greatest common divisor of all the toll charges that Charles pays for that day. If Charles does not have to pay in any of the tolls, the answer is 0.
Input
The first line of the input gives the number of test cases, T. T test cases follow.
The first line of each test case contains the two integers N and Q.
The next N−1 lines describe the roads. The i-th of these lines contains the four space-separated integers X, Y, Li, and Ai, indicating a road between cities X and Y with load-limit Li and toll charge Ai.
The next Q lines describe the queries. The j-th of these lines contains the two space-separated integers Cj and Wj representing the starting city and the weight of the load on the j-th day.
Output
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is a list of the answers for the Q days in order, separated by spaces.
Constraints
- 1 ≤ T ≤ 100.
- 1 ≤ Li ≤ 2 × 10^5, for all i.
- 1 ≤ Ai ≤ 10^18, for all i.
- All Li are distinct.
- 2 ≤ Cj ≤ N, for all j.
- 1 ≤ Wj ≤ 2 × 10^5, for all j.
- It is guaranteed that the given roads form a tree.
Hint
In Sample Case #1
On the first day, Charles pays toll charges in the roads between cities (5,3), (3,2), and (2,1). The answer is gcd(9,8,4) = 1.
On the second day, Charles pays toll charges in the roads between cities (3,2) and (2,1). The answer is gcd(8,4) = 4.
On the third day, Charles does not pay toll charges in any of the cities. Thus, the answer is 0.
In Sample Case #2
On the first day, Charles pays toll charges in the roads between cities (2,1). The answer is 10.
On the second day, Charles pays toll charges in the roads between cities (3,2) and (2,1). The answer is gcd(5,10) = 5.