34246번 - 모임과 쿼리

문제

가중치 있는 트리 구조의 마을에서 1ドル$번부터 $N$번까지 $N$명의 사람들이 살고 있다. $i$번 사람은 $i$번 정점에 살고 있다.

사람들은 모임을 $Q$번 갖는데, $k$번째 모임에서는 1ドル$ 이상 $N$ 이하의 원하는 정수 $x_k$를 골라 번호가 $\ell_k$ 이상 $r_k$ 이하인 사람들이 참여한다.

$k$번째 모임에 걸리는 시간 $t_k$는 모임에 참여하는 각 사람과 $x_k$까지의 거리 중 최댓값이다.

$t_k$가 최소가 되도록 $x_k$를 고를 때, 각 모임에 걸리는 시간 $t_k$를 계산해 보자.

입력

첫째 줄에 사람들의 수 $N$과 모임의 수 $Q$가 공백으로 구분되어 주어진다. (1ドル \le N, Q \le 100,000円$)

다음 $N-1$개 줄 중 $i$번째 줄에는 트리의 간선 정보를 나타내는 정수 $a_i,ドル $b_i,ドル $c_i$가 공백으로 구분되어 주어진다. 이는 $a_i$번 정점과 $b_i$번 정점을 잇는 가중치가 $c_i$인 간선이 있다는 뜻이다. (1ドル \le a_i, b_i \le N,ドル 1ドル \le c_i \le 10^9,ドル $a_i \ne b_i$)

다음 $Q$개 줄 중 $k$번째 줄에는 $k$번째 모임에 참여하는 사람들의 번호 범위를 나타내는 정수 $\ell_k,ドル $r_k$가 공백으로 구분되어 주어진다. (1ドル \le \ell_k \le r_k \le N$)

출력

각 모임마다 모임에 걸리는 시간 $t_k$를 한 줄에 출력한다.

제한

힌트