시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 512 MB | 399 | 97 | 77 | 22.319% |
정점이 N개인 트리가 주어진다. 각 정점은 1번부터 N번까지 차례대로 번호가 부여되어 있다. i번째 간선은 Ai번 정점과 Bi번 정점을 연결하며, 가중치는 Ci다(1 ≤ i < N).
트리에서 두 정점 사이의 거리는 그 둘을 잇는 최단경로 상의 간선의 가중치의 최댓값으로 정의한다. 단, 같은 두 정점 사이의 거리는 0으로 정의한다.
트리에 사는 사람들이 Q개의 모임을 개최하려 한다. i번째 모임에는 Si 이상 Ei 이하의 번호를 가진 정점에 사는 사람들이 참석한다. 각 모임은 트리 상의 어떤 정점 v에서 이루어진다. 사람들이 모이는 정점 v를 잘 정하여, 모임에 참석하는 각 사람이 정점 v까지 이동하는 거리의 최댓값을 최소화하고자 한다.
이때 이 최솟값을 구하는 프로그램을 작성하시오.
첫 번째 줄에 트리의 정점 개수를 의미하는 자연수 N과 모임이 개최되는 횟수를 의미하는 자연수 Q가 사이에 공백을 두고 주어진다.
두번째 줄부터 (N-1)개의 줄에 걸쳐, 트리의 간선에 관한 정보가 주어진다. (i+1)번째 줄에는 세 개의 자연수 Ai, Bi, Ci가 사이에 공백을 두고 주어진다(1 ≤ i < N). 이는 Ai번 정점과 Bi번 정점을 연결하는 가중치 Ci의 간선이 존재함을 의미한다.
(N+1)번째 줄부터 Q개의 줄에 걸쳐, Q개의 모임에 관한 정보가 주어진다. (N+i)번째 줄에는 i번째 모임을 나타내는 두 개의 자연수 Si와 Ei가 사이에 공백을 두고 주어진다(1 ≤ i ≤ Q).
첫 번째 줄부터 Q개의 줄에 걸쳐, 답을 차례대로 출력한다. i번째 줄에는 i번째 모임에 대한 답을 출력한다(1 ≤ i ≤ Q).
모든 입력 데이터는 다음 조건을 만족한다.
3 3 1 2 1 2 3 2 1 2 2 3 1 3
1 2 2
High School > 경기과학고등학교 > 나는코더다 2019 송년대회 L번