[BOJ] 15481번: 그래프와 MST

https://www.acmicpc.net/problem/15481

일단 주어진 그래프에서 MST를 만들어둡시다. 이제 u와 v를 연결하는 edge를 포함하는 MST를 생각하면, 기존의 MST에서 u에서 v로 가는 경로 상에 있는 간선 중에 가장 비용이 큰 것을 잘라내고 해당 edge를 편입시키면 됩니다. 엄밀한 증명은 독자에게 맡긴다! 간선의 비용이 동적으로 변하는 상황이 아니므로 굳이 HLD를 쓸 필요 없이 sparse table을 응용하면 됩니다.

https://github.com/blisstoner/BOJ/blob/master/15481.cpp