정기 모임

시간 제한2초메모리 제한512 MB

요약

가중치가 있는 트리에서 각 질의마다 번호 S부터 E까지의 정점에 사는 사람들이 모일 때, 가장 먼 사람까지의 거리가 가장 작아지는 값을 구합니다.

난이도: 보통10점 중 7점
유형: 트리, 유니온 파인드, 세그먼트 트리
정답자: 아직 제출이 없습니다

문제

정점이 $N$ 개인 트리가 주어진다. 각 정점은 1번부터 $N$ 번까지 차례대로 번호가 부여되어 있다. $i$ 번째 간선은 $A_i$ 번 정점과 $B_i$ 번 정점을 연결하며, 가중치는 $C_i$ 다 ( $1 \le i < N$ ).

트리에서 두 정점 사이의 거리는 그 둘을 잇는 최단경로 상의 간선 가중치의 최댓값으로 정의한다. 같은 두 정점 사이의 거리는 0으로 정의한다.

트리에 사는 사람들이 $Q$ 개의 모임을 개최하려 한다. $i$ 번째 모임에는 번호가 $S_i$ 이상 $E_i$ 이하인 정점에 사는 사람들이 참석한다. 각 모임은 트리 위의 어떤 정점 $v$ 에서 열린다. 참석자 모두가 $v$ 까지 이동하는 거리의 최댓값이 가장 작아지도록 $v$ 를 정한다.

이때 이 최솟값을 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 정점의 개수 $N$ 과 모임의 횟수 $Q$ 가 공백으로 구분되어 주어진다. 두 번째 줄부터 $N-1$ 개의 줄에 간선 정보가 주어진다. $i+1$ 번째 줄에는 자연수 $A_i$ , $B_i$ , $C_i$ 가 공백으로 구분되어 주어지며, 이는 $A_i$ 번 정점과 $B_i$ 번 정점을 잇는 가중치 $C_i$ 의 간선이 있다는 뜻이다. $N+1$ 번째 줄부터 $Q$ 개의 줄에 모임 정보가 주어진다. $N+i$ 번째 줄에는 $i$ 번째 모임을 나타내는 자연수 $S_i$ 와 $E_i$ 가 공백으로 구분되어 주어진다.

출력

첫 번째 줄부터 $Q$ 개의 줄에 걸쳐 답을 차례대로 출력한다. $i$ 번째 줄에는 $i$ 번째 모임의 답을 출력한다.

제한

$1 \le N \le 300,000$
$1 \le Q \le 300,000$
$1 \le A_i \le N$ ( $1 \le i < N$ )
$1 \le B_i \le N$ ( $1 \le i < N$ )
$A_i \ne B_i$ ( $1 \le i < N$ )
$1 \le C_i \le 10^9$ ( $1 \le i < N$ )
$1 \le S_i \le E_i \le N$ ( $1 \le i \le Q$ )

예제1

예제 1
입력
```
3 3
1 2 1
2 3 2
1 2
2 3
1 3
```
예상 출력
```
1
2
2
```