7186 : 전력망 분리
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
N개의 송전탑이 트리 구조로 연결되어 있습니다. 이 중 전선 하나를 끊어서 전력망을 둘로 분할할 때, 두 전력망의 송전탑 개수 차이의 최솟값을 구하십시오.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 송전탑(노드)의 개수 N이 주어집니다. (2 ≤ N ≤ 100)
둘째 줄부터 N-1개의 줄에 걸쳐 전선으로 연결된 두 송전탑의 번호가 주어집니다.
둘째 줄부터 N-1개의 줄에 걸쳐 전선으로 연결된 두 송전탑의 번호가 주어집니다.
출력 설명
분리된 두 전력망의 노드 개수 차이의 최솟값을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
9
1 3
2 3
3 4
4 5
4 6
4 7
7 8
7 9
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3도움
3-4 사이의 전선을 끊으면 {1, 2, 3} (3개) 와 {4, 5, 6, 7, 8, 9} (6개) 로 분할되어 차이의 최솟값은 3입니다. (4-7 끊을 시 {7, 8, 9}(3)와 {1,2,3,4,5,6}(6) 도 차이 3)