Ravnica

시간 제한1초메모리 제한1024 MB

요약

도시 N개로 이루어진 트리에서 각 도시의 남은 도로 수가 2 이하가 되도록 지워야 하는 최소 도로 수를 구한다.

난이도: 보통10점 중 6점
유형: 트리, 동적 계획법, DFS
정답자: 아직 제출이 없습니다

문제

U jednom maloj državi živi Stjepan, čovjek koji mrzi raskrižja. Stjepan je nedavno postao apsolutni vladar države te je odlučio da će prva stvar koju će napraviti na vlasti biti uništavanje cesta kako više ne bi bilo raskrižja.

Država se sastoji od $N$ gradova i $N-1$ cesta između gradova. Između svaka dva grada moguće je doći nekim jedinstvenim nizom cesta. Stjepan sada želi uništiti neke ceste tako da nakon uništavanja svaki grad ima iz sebe najviše dvije ceste.

Iako će uništavati ceste, Stjepan je dobar čovjek i ne želi puno problema pa će uništiti najmanji mogući broj cesta tako da ostvari svoj cilj. Odredite broj cesta koje će Stjepan uništiti.

입력

U prvom je retku prirodan broj $N$ ( $2 ≤ N ≤ 100\\,000$ ), broj gradova.

U sljedećih $N-1$ redaka nalaze se dva različita prirodna broja $A$ i $B$ ( $1 ≤ A, B ≤ N$ ), oznake gradova koje spaja $i$ -ta cesta.

출력

U prvi redak ispiši traženi broj iz zadatka.

힌트

Opis prvog probnog primjera: Stjepan može npr. uništiti cestu između grada $1$ i grada $2$ .

예제2

예제 1
입력
```
5
1 2
1 3
2 4
2 5
```
예상 출력
```
1
```
예제 2
입력
```
7
1 2
1 3
2 4
2 5
3 6
3 7
```
예상 출력
```
2
```