Informatica Online Judge

  도로길이 구하기3 [1705 / 06A9]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 33   Total Tried : 53


The Champion of this Problem (C++) : gs17044 - ms / 1545byte
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]

Background

N개의 도시와 도시사이를 연결하는 유일한 도로가 N-1개의 도로가 있다.

두 도시를 연결하는 경로 상에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 구하는 프로그램을 작성하시오.(총 K개의 도시 쌍이 주어진다.)

Input

첫 번째 줄에는 도시개수인 N이 입력된다. (2 ≤ N ≤ 100,000)
두 번째 줄부터 N-1 개의 줄에는 도시 2개와 그 도시 사이를 연결하는 도로길이 M을 입력한다. (1≤ M ≤ 1,000,000)
다음 줄에는 K가 주어진다. (1 ≤ K ≤ 100,000)
K개 줄에는 도로가 연결되어 있는 두 도시 A와 B를 입력한다.

Output

A와 B 도시를 연결하는 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 순서대로 출력한다.

IO Example

<입력>
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

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]