문제
정올국은 N개의 도시가 트리 형태로 연결되어 있는 모양이다. 각 도로는 현재 전체적으로 노후되어 있기에 정올국의 대통령인 준혁이는 돈을 들여 도로를 개선하기로 한다.
i번째 도로는 현재 제한 속도 si, 개선하는데 드는 비용 ci, 개선 뒤 제한 속도 vi의 세 정수로 표현할 수 있다. 이때 si<vi를 항상 만족한다.
도로 개선 계획이 Q개 수립되었다. 각 계획은 도시 두개 ui와 vi와 사용 가능 비용 ei로 표현할 수 있는데, ui와 vi를 잇는 경로상의 도로를 최대 ei의 비용을 사용하여 개선하겠다는 뜻이다. 이때 개선 방법은 ui와 vi를 잇는 도로 상의 최소 제한 속도를 최대화하는 방법으로 하기로 했다.
각 개선 계획에 대해 ui와 vi를 잇는 도로 상의 최소 제한 속도를 최대 ei의 비용을 사용해서 최대화하여라.
입력
첫 줄에 도시의 개수 N (1<=N<=100000)이 주어진다.
그 다음 N-1줄에 걸쳐 도로의 정보 xi, yi, si, ci, vi가 순서대로 주어진다. 이는 xi와 yi 사이를 잇는 도로의 정보를 뜻한다. (1<=si<vi<=10^9, 1<=ci<=10^9)
그 다음 개선 계획의 개수 Q(1<=Q<=100000)이 주어진다.
그 다음 Q줄에 걸쳐 개선 계획 ui, vi, ei가 주어진다. (1<=ei<=10^18)
출력
Q줄에 걸쳐 각 쿼리의 답을 출력하시오.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 21점 | N, Q<=1000 |
| #2 | 29점 | 각 도시는 최대 2개의 다른 도시와 연결되어있다. |
| #3 | 60점 | 제한 없음 |
예제 #1
6
1 2 5 7 10
1 3 4 8 9
3 4 7 1 15
3 5 6 3 11
3 6 5 6 8
3
2 4 15
6 4 5
3 5 10
7
5
11
예제 #2
4
1 2 5 5 8
2 3 4 6 9
3 4 6 10 7
4
1 4 16
2 4 16
1 4 10
3 4 10
6
7
5
7
출처
COCI 2022/2023 Contest #4 4번
로그인해야 코드를 작성할 수 있어요.