트럭 배달
메모리 제한1024 MB
루트가 1인 트리에서 각 질의 (도시 C, 무게 W)마다 C에서 루트까지 가는 경로 중 하중 한계가 W 이하인 간선의 통행료 최대공약수를 구하고, 해당 간선이 없으면 0을 출력한다.
문제
Charles는 Googleland 시의 트럭 운전사다. Googleland는 N개의 노드로 이루어진 트리 형태로, 각 노드는 도시를, 각 간선은 두 도시를 잇는 도로를 나타낸다. 도시는 1번부터 N번까지 번호가 붙어 있다. Googleland의 수도는 1번 도시다. Charles는 매일 C번 도시에서 무게 W인 짐을 실어 두 도시 사이의 유일한 단순 경로를 따라 1번 도시로 배달하려고 한다. 각 도로 i에는 통행료가 있으며, 짐의 무게가 적재 한계 Li 이상이면 통행료 Ai를 부과한다.
Charles는 Q일 동안 일하며, 각 날짜마다 출발 도시 C와 짐의 무게 W가 주어진다. 각 날짜마다 Charles가 지불하는 모든 통행료의 최대공약수를 구하라. 어느 통행료도 지불할 필요가 없으면 답은 0이다.
입력
입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. T개의 테스트 케이스가 이어진다.
각 테스트 케이스의 첫 줄에는 두 정수 N과 Q가 주어진다.
다음 N−1개의 줄은 도로를 나타낸다. 이 중 i번째 줄에는 네 개의 정수 X, Y, Li, Ai가 공백으로 구분되어 주어지며, 이는 도시 X와 Y 사이에 적재 한계 Li, 통행료 Ai인 도로가 있음을 나타낸다.
다음 Q개의 줄은 질의를 나타낸다. 이 중 j번째 줄에는 두 정수 Cj와 Wj가 공백으로 구분되어 주어지며, 이는 j번째 날의 출발 도시와 짐의 무게를 나타낸다.
출력
각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 Q일 동안의 답을 순서대로 공백으로 구분한 목록이다.
제한
- 1 ≤ T ≤ 100.
- 모든 i에 대해 1 ≤ Li ≤ 2 × 10^5.
- 모든 i에 대해 1 ≤ Ai ≤ 10^18.
- 모든 Li는 서로 다르다.
- 모든 j에 대해 2 ≤ Cj ≤ N.
- 모든 j에 대해 1 ≤ Wj ≤ 2 × 10^5.
- 주어진 도로는 트리를 이룬다.
힌트
예제 1에서
첫째 날 Charles는 도시 (5,3), (3,2), (2,1) 사이의 도로에 대한 통행료를 지불한다. 답은 gcd(9,8,4) = 1이다.
둘째 날 Charles는 도시 (3,2), (2,1) 사이의 도로에 대한 통행료를 지불한다. 답은 gcd(8,4) = 4이다.
셋째 날 Charles는 어느 도시에서도 통행료를 지불할 필요가 없다. 따라서 답은 0이다.
예제 2에서
첫째 날 Charles는 도시 (2,1) 사이의 도로에 대한 통행료를 지불한다. 답은 10이다.
둘째 날 Charles는 도시 (3,2), (2,1) 사이의 도로에 대한 통행료를 지불한다. 답은 gcd(5,10) = 5이다.