마을의 도로가 주어졌을 때, 이 마을을 2개의 마을로 분할했을 때의 도로 유지비의 합의 최소값을 구하는 문제입니다. 여기서 분할의 기준은 두 마을 사이의 경로가 존재하지 않음을 의미합니다. 이 문제에서 달성해야 할 목적은 2가지입니다. 첫 번째는 도로의 유지비를 줄이는 것, 두 번째는 마을을 2개로 분할하는 것입니다. 첫 번째는 MST로 어렵지 않게 구할 수 있지만 두 번째는 조금 힘들어보입니다. 하지만 조금만 더 생각해보면 MST를 만든 상태에서 길을 하나만 지우면 무조건 마을이 2개로 분할된다는 것을 떠올릴 수 있습니다. 트리(MST의 T가 트리입니다!)의 특성 상 간선을 하나 지울 때마다 무조건 트리가 분할됩니다. 따라서 MST를 만들고 그 중 가장 가중치가 큰 도로를 하나 지우면 마을을 2개로 분할하고 도로의 유지비가 최소인 경우를 찾을 수 있을 것입니다.
PS알못 OrbitHv의 PS