Problem
n 꼭지점으로 구성된 트리(연결된 비순환 무향 그래프)가 제공됩니다.
최대 일치 크기(쌍으로 인접하지 않은 가장자리 집합)를 찾습니다.
입력:
첫 번째 줄에는 트리의 정점 수인 숫자 n이 포함됩니다.
그 다음에는 n-1줄이 나오며, 각 줄에는 두 개의 숫자 a
i 및 b
i(1 <= a
i, b
i <= n) - 트리 가장자리.
출력:
하나의 숫자 인쇄 - 주어진 트리의 최대 일치 크기.
예:
<몸>
| 입력 |
출력 |
4
1 2
23
3 4 |
2 |
설명:
이 트리의 최대 일치에는 에지 1-2 및 3-4가 포함됩니다.