도로 네트워크
시간 제한2초메모리 제한512 MB
트리가 주어질 때 간선 하나를 추가한 뒤 남는 단절선의 수가 최소가 되도록 만들고, 그 최솟값을 구한다.
문제
적과의 치열한 싸움 끝에 브루스 웨인은 마침내 선거에서 승리해 고담의 시장이 되었다. 여느 정치인처럼 그는 고담의 번영을 위해 많은 사업을 담은 계획을 세웠지만, 똑같은 문제에 부딪혔다. 자금이 부족했다.
그는 문제를 다른 관점에서 해결하기로 했다. 기업들이 도시의 도로를 살 수 있게 해주는 것이다(도시의 도로는 무방향이다). 도시는 사업에 필요한 돈을 얻고, 기업은 도로를 광고에 사용할 수 있다(그는 그렇게 생각했다).
거래가 끝난 뒤, 기업들은 그의 예상보다 교활했다. 기업들은 도시의 도로를 정확히 하나 막아 사람들이 출근하지 못하게 만들겠다고 협박하기 시작했고, 사람들이 웨인 시장에게 반란을 일으키기를 바랐다. 문제는 도시가 연결된 구역들의 트리로 설계되어 있어, 어떤 두 구역 사이에도 유일한 경로가 하나뿐이라는 점이었다. 따라서 도로 하나를 막으면 어떤 구역들은 다른 구역에 더 이상 도달할 수 없게 된다.
웨인 시장은 의회와 이 문제를 논의하고 취약한 도로라고 부르는 것을 정의했다. 도로를 막았을 때 두 구역이 서로 분리될 수 있다면 그 도로는 취약하다. 웨인 시장은 도로를 더 지어 이런 일이 일어나지 않게 하려 하지만, 예산으로는 도로를 하나만 더 지을 수 있다. 취약한 도로의 수를 최소화하려면 어떤 도로를 지어야 하는지 알려줄 수 있는가?
입력
프로그램은 하나 이상의 테스트 케이스에 대해 실행된다. 입력의 첫 줄에는 테스트 케이스의 수 T가 정수 하나로 주어지고(1 ≤ T ≤ 100), 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 도시의 구역 수 N이 정수 하나로 주어진다(1 ≤ N ≤ 10, 000). 다음 N − 1개의 줄에는 각각 정수 x와 y가 공백 하나로 구분되어 주어지는데(1 ≤ x, y ≤ N), 구역 x가 구역 y와 연결되어 있다는 뜻이다. 간선들은 트리를 이룬다.
출력
각 테스트 케이스마다 새 도로를 지은 뒤 도시에 남은 취약한 도로 수의 최솟값을 정수 하나로 출력한다.