23979번 - 트리의 재구성

정점 N개로 이루어진 트리가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있고, 트리의 간선은 양방향이며 각 간선마다 비용이 모두 다르다.

다음과 같은 쿼리를 수행하는 프로그램을 작성하여라.

• u v w a b: u에서 v로 가는 비용이 w인 간선을 잇는다. 지웠을 때 트리가 되는 간선 중 새로 추가한 간선을 제외한 비용이 가장 큰 간선 하나를 지운다. 재구성된 트리의 a에서 b로 가는 경로의 비용을 출력한다.

각 쿼리가 끝나면 트리는 처음 상태로 돌아간다.

첫째 줄에 정점의 개수 N과 쿼리의 개수 Q가 주어진다. (2 ≤ N, Q ≤ 100,000)

둘째 줄부터 N-1개의 줄에 두 정점과 두 정점을 잇는 간선의 비용인 정수 C가 주어진다. (1 ≤ C ≤ 200,000)

다음 줄부터 각 쿼리의 u, v, w, a, b가 주어진다. (1 ≤ w ≤ 200,000, u ≠ v)

각 쿼리의 답을 출력한다.