23006번 - Truck Delivery 서브태스크다국어

Charles is a truck driver in the city of Googleland. Googleland is built in 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 using the simple path (which is unique) between the cities. Each road i has a toll which charges amount A_i if the weight of the load is greater than or equal to a load-limit L_i.

Charles works for Q days, where for each day Charles will be given the starting city C and 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 did not have to pay in any of the tolls the answer is 0.

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. i-th of these lines contains the four space separated integers X, Y, L_i and A_i, indicating a road between cities X and Y with load-limit L_i and toll charge A_i.

The next Q lines describe the queries. j-th of these lines contains the two space separated integers C_j and W_j representing the starting city and weight of the load on j-th day.

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 Q days in order, separated by spaces.

• 1 ≤ T ≤ 100.
• 1 ≤ L_i ≤ 2 × 10⁵, for all i.
• 1 ≤ A_i ≤ 10¹⁸, for all i.
• All L_i are distinct.
• 2 ≤ C_j ≤ N, for all j.
• 1 ≤ W_j ≤ 2 × 10⁵, for all j.
• It is guaranteed that given roads form a tree.

시간 제한: 20 초

• 2 ≤ N ≤ 1000.
• 1 ≤ Q ≤ 1000.

시간 제한: 80 초

• 2 ≤ N ≤ 5 × 10⁴ and 1 ≤ Q ≤ 10⁵ for at most 20 test cases.
• For the remaining cases, 2 ≤ N ≤ 1000 and 1 ≤ Q ≤ 1000.

In Sample Case #1

On the first day, Charles should pay toll charges in the roads between cities (5,3), (3,2) and (2,1). The answer will be gcd(9,8,4) = 1.

On the second day, Charles should pay toll charges in the roads between cities (3,2) and (2,1). The answer will be gcd(8,4) = 4.

On the third day, Charles need not pay toll charges in any of the cities. Thus, the answer will be 0.

In Sample Case #2

On the first day, Charles should pay toll charges in the roads between cities (2,1). The answer will be 10.

On the second day, Charles should pay toll charges in the roads between cities (3,2) and (2,1). The answer will be gcd(5,10) = 5.