정올국은 N개의 도시가 트리 형태로 연결되어 있는 모양이다. 각 도로는 현재 전체적으로 노후되어 있기에 정올국의 대통령인 준혁이는 돈을 들여 도로를 개선하기로 한다.

i번째 도로는 현재 제한 속도 si, 개선하는데 드는 비용 ci, 개선 뒤 제한 속도 vi의 세 정수로 표현할 수 있다. 이때 si<vi를 항상 만족한다.

도로 개선 계획이 Q개 수립되었다. 각 계획은 도시 두개 ui와 vi와 사용 가능 비용 ei로 표현할 수 있는데, ui와 vi를 잇는 경로상의 도로를 최대 ei의 비용을 사용하여 개선하겠다는 뜻이다. 이때 개선 방법은 ui와 vi를 잇는 도로 상의 최소 제한 속도를 최대화하는 방법으로 하기로 했다.

각 개선 계획에 대해 ui와 vi를 잇는 도로 상의 최소 제한 속도를 최대 ei의 비용을 사용해서 최대화하여라.

#5489 upload 5 done 1 how_to_reg 1 call_split Subtask

도로 개선 timer 3s memory 1024MB

#5489
Subtask

도로 개선 3s 1024MB