"일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다."
각 마을 안에 있는 집들이 모두 연결되도록 길을 구성했는데 서로 다른 마을 사이를 연결하는 길이 있었다고 합시다.
이 상황에서 이 길을 제외해도 문제의 조건에 맞게 길을 구성할 수 있습니다. 서로 다른 마을 사이를 연결하는 길을 없애든 없애지 않든 각 마을 안에 있는 집끼리의 연결 여부는 변하지 않을 것이기 때문입니다.
문제에서 요구한 것은 남은 길 유지비의 합의 최솟값이니, 이 길을 제외하지 않으면 반드시 손해이며 (모든 길의 유지비는 양수니까요) 없애야만 한다는 것을 논리적으로 유추할 수 있습니다.

ksjb2897 1년 전
두 마을로 쪼개서 각 마을안에서 집들이 서로 연결되어야 한다고 나와있는데, 그 연결된다고 하는 길도 전부 한 마을에 있어야 하나요?
각 마을에서 임의의 2개의 집이 연결되어야 한다고 하는데, A마을 -> B마을 -> A마을 이렇게 순회하는 경로도 연결되어있다고 봐야할지 아닐지 모르겠어요. 문제에 다른마을간의 경로는 모두 빼도된다. 라고 나와있는거 보면 순회하는 경로는 제외해야한다고 생각이 들긴하는데, 일단 애매모호해서 질문드립니다!