| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 162 | 57 | 47 | 35.338% |
정점 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)
각 쿼리의 답을 출력한다.
10 5 1 3 3 3 2 7 4 1 9 1 6 2 6 8 4 8 9 10 3 5 5 5 7 8 10 5 1 10 8 6 7 9 2 5 13 2 3 1 9 11 1 9 5 1 12 10 2 3 5 17 5 4
25 18 11 23 29