Informatica Online Judge

  가정방문 [2144 / 0860]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 1   Total Tried : 2


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[34th 김진영]
Writer ID : [gs16020]

Background

인자하고 자상하신 Ms. Catty 선생님은 오늘자 가정방문으로 I번째 학생의 집에서 J번째 학생의 집까지 순서대로 방문하기로 했다.

그런데 우리 Ms. Catty 선생님은 학생들을 배려해서 한 가정방문이 끝나고 다음 학생의 가정방문을 갈 때, 그 학생에게 얼마만큼의 시간이 걸릴지 미리 전화로 알려준다.

그리고 가장 긴 시간이 걸리는 집은 미안함의 의미로 그 학생이 좋아하는 물건을 하나 주려고 한다.

그런데 Ms. Catty 선생님은 머리가 나빠서 이전 집에서 도착하기까지 가장 긴 시간이 걸리는 집의 학생이 누군지 미리 파악해두지 않았다.

불쌍한 Ms. Catty 선생님을 도와 도착하기까지 가장 긴 시간이 걸리는 집의 학생이 누군지 알려주자.

단, Ms. Catty 선생님의 마을은 매우 단조로워서 모든 집이 트리 형태로 연결되어 있다.

Input

첫 번째 줄에 Ms. Catty 선생님 반의 학생 수 N과 범위에 대한 질의의 개수 Q가 주어진다.
(2<=N<=200,000, 1<=Q<=200,000)

두 번째 줄부터 N-1줄에 걸쳐서 학생들 집의 연결정보와 소요시간 a,b,c가 주어진다. 즉 a학생의 집에서 b학생의 집까지 c만큼 시간이 걸리는 도로로 연결되어 있다는 의미이다.

물론 도로는 양방향 통행이며 집들은 트리를 이룬다.
(1<=a,b<=n, a!=b,1<=c<=5000)

N+1번째 줄부터 Q줄에 걸쳐서 오늘 가정방문을 할 집의 범위 i,j가 주어진다.

즉 i학생부터 j학생까지 번호순으로 방문할 예정이라는 의미이다.
(1<= i < j<= n)

Output

Q줄에 걸쳐 각 질의의 i학생부터 j학생까지 번호 순으로 가정방문을 할 때 바로 직전의 집에서 도착하기까지 가장 긴 시간이 소요되는 학생의 번호를 순서대로 출력하라.

물론 Ms. Catty 선생님은 언제나 최단경로로 간다. (첫 번째 방문 학생은 소요시간을 0으로 한다.)

만약 그러한 학생이 유일하지 않다면 “Too Many Students!”를 출력하라. (큰따옴표는 제외하고 출력하라.)

IO Example

입력1
5 4
1 2 3
1 3 4
2 4 1
2 5 2
1 2
1 3
3 5
1 5

출력1
2
3
4
4


입력2
5 2
1 3 1
1 4 1
2 3 1
3 5 2
2 5
1 4

출력2
5
Too Many Students!

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