도로 네트워크

시간 제한1초메모리 제한256 MB

요약
가중치가 있는 트리에서 두 노드 사이 경로에 놓인 도로 중 최소 길이와 최대 길이를 여러 번 질의에 답해 구한다.
난이도

보통10점 중 6점

유형
트리, 이분 탐색, 그래프
정답자
아직 제출이 없습니다

문제

N개의 도시와 도시들을 연결하는 N - 1개의 도로로 이루어진 도로 네트워크가 있다.

임의의 두 도시 사이에는 두 도시를 연결하는 경로가 정확히 하나 존재한다. 각 도로의 길이는 입력으로 주어진다.

K개의 도시 쌍이 주어진다. 각 쌍에 대해, 두 도시를 연결하는 경로 위에 있는 도로들 중 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 구하라.

입력

첫째 줄에 N (2 <= N <= 100,000)이 주어진다.

다음 N - 1개 줄에는 도로를 나타내는 세 정수 A, B, C가 주어진다. 이는 도시 A와 도시 B 사이에 길이가 C인 도로가 있다는 뜻이다. 도로의 길이는 1,000,000 이하의 양의 정수이다.

다음 줄에 K (1 <= K <= 100,000)가 주어진다.

다음 K개 줄에는 서로 다른 두 자연수 D와 E가 주어진다. 각 쌍에 대해 D와 E를 연결하는 경로에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 출력해야 한다.

출력

총 K개 줄을 출력한다. 각 줄에는 해당 질의의 두 도시 D와 E를 연결하는 경로에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 출력한다.

예제3

  1. 예제 1

    입력
    5
2 3 100
4 3 200
1 5 150
1 3 50
3
2 4
3 5
1 2
    예상 출력
    100 200
50 150
50 100

  2. 예제 2

    입력
    7
3 6 4
1 7 1
1 3 2
1 2 6
2 5 4
2 4 4
5
6 4
7 6
1 2
1 3
3 5
    예상 출력
    2 6
1 4
6 6
2 2
2 6

  3. 예제 3

    입력
    9
1 2 2
2 3 1
3 4 5
2 7 4
1 5 3
5 6 1
5 9 2
1 8 3
5
6 9
7 8
9 4
1 2
7 3
    예상 출력
    1 2
2 4
1 5
2 2
1 4