페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8640

모임과 쿼리 3s 1024MB

문제

가중치 있는 트리 구조의 마을에서 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를 한 줄에 출력한다.


예제 

5 3
1 2 2
1 4 5
1 3 2
4 5 6
2 3
1 5
4 5
2
7
6


출처

eggx50000
로그인해야 코드를 작성할 수 있어요.