\(N\)개의 정점으로 이루어진 트리가 주어진다.
트리의 각 간선에는 가중치가 있다.

\(Q\)개의 질의가 주어진다.
각 질의마다 두 정점 \(a\), \(b\)가 주어질 때, 정점 \(a\)에서 정점 \(b\)로 가는 단순 경로 위에 있는 간선들의 가중치 중 최댓값을 출력하시오.

단, \(a = b\)인 경우 지나가는 간선이 없으므로 \(0\)을 출력한다.

\(2 \le N \le 200\,000\)
\(1 \le Q \le 200\,000\)
\(1 \le a, b \le N\)
\(1 \le w \le 10^9\)
주어지는 그래프는 트리이다.

첫째 줄에 정점의 개수 \(N\)과 질의의 개수 \(Q\)가 주어진다.

둘째 줄부터 \(N-1\)개의 줄에는 간선 정보 \(a\ b\ w\)가 주어진다.

이는 정점 \(a\)와 정점 \(b\)가 가중치 \(w\)인 간선으로 연결되어 있다는 뜻이다.

그 다음 줄부터 \(Q\)개의 줄에는 질의 \(a\ b\)가 주어진다.

각 질의마다 정점 \(a\)에서 정점 \(b\)로 가는 경로 위 간선 가중치의 최댓값을 한 줄에 하나씩 출력한다.

anthony0506 작성

출처 anthony0506