정기 모임
시간 제한2초메모리 제한512 MB
가중치 트리에서 두 정점 사이 거리를 경로 위 간선 가중치의 최댓값으로 정의할 때, 각 구간 [S,E]에 속한 정점들을 한 점 v로 모으는 최대 거리의 최솟값을 Q개의 질의마다 구한다.
문제
정점이 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).
제한
모든 입력 데이터는 다음 조건을 만족한다.
- 1 ≤ N ≤ 300,000
- 1 ≤ Q ≤ 300,000
- 1 ≤ Ai ≤ N (1 ≤ i < N)
- 1 ≤ Bi ≤ N (1 ≤ i < N)
- Ai ≠ Bi (1 ≤ i < N)
- 1 ≤ Ci ≤ 109 (1 ≤ i < N)
- 1 ≤ Si ≤ Ei ≤ N (1 ≤ i ≤ Q)