상수는 그래프 하나를 가지고 있습니다.

이 그래프는 무방향 가중치 그래프입니다.

또한 이 그래프는 N개의 정점과 M개의 간선을 가지고 있습니다.

상수는 이 그래프의 최소 신장 트리의 값을 알고 싶어 합니다. (최소 신장 트리의 값이란 최소 신장 트리를 이루는 모든 간선 가중치들을 합친 것을 의미합니다.)

하지만 이 그래프는 상수의 성격만큼이나 변덕스러워서 상수가 그래프의 최소 신장 트리를 구하기도 전에 자신의 간선 가중치 하나를 바꾸어 버립니다!

상수는 최소 신장 트리를 구하기 위해 그래프를 설득해 보았지만

그래프는 어떤 간선의 가중치를 몇으로 바꿀 것인지에 대한 정보를 상수에게는 안 주고(...) 프로그래밍을 잘 하는 여러분에게 주었다고 하네요.

여러분은 그래프가 어떤 간선의 가중치를 몇으로 바꿀지에 대한 정보를 Q개 입수했습니다.

여러분은 이 Q개의 쌍에 대해 각각 최소 신장 트리의 가중치를 구해 상수를 도와 주세요!

가중치는 여러분이 최소 신장 트리를 구하면 원래대로 돌아옵니다.

즉 여러분이 다룰 그래프는 원래 그래프와 가중치 하나가 다를 뿐입니다.

상수와 그래프 timer 1s memory - MB

상수와 그래프 1s - MB