Servade kustutamine

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

요약

트리가 주어질 때, 모든 연결 요소가 짝수 트리(잎 사이의 모든 경로 길이가 짝수)가 되도록 제거할 최소 간선 수를 구한다.

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

문제

Graafiteoorias nimetatakse puuks sidusat tsükliteta graafi. Leheks nimetatakse puu tippu, millest väljub ainult üks serv. Puud nimetatakse paarispuuks, kui ükski tee selle lehtede vahel ei koosne paaritust arvust servadest. Ka ühe tipu (ja null servaga) puu loetakse paarispuuks.

Kui puust mõni serv kustutada, saame mittesidusa graafi, mille iga sidususkomponent on omakorda puu. Selles ülesandes on antud puu $G$ ja vaja on leida minimaalne hulk servi, mille eemaldamisega saame paarismetsa: graafi, mille kõik sidususkomponendid on paarispuud.

입력

Sisendi esimesel real on graafi $G$ tippude arv $N$ ( $1 \le N \le 10^6$ ). Graafi tipud on nummerdatud $1 \ldots N$ . Järgmisel $N - 1$ real on igaühel kaks tühikuga eraldatud täisarvu $U\_i$ ja $V\_i$ ( $1 \le U\_i \le N$ , $1 \le V\_i \le N$ , $U\_i \ne V\_i$ ), mis näitavad, et graafi tippude $U\_i$ ja $V\_i$ vahel on serv. Võib eeldada, et $G$ on kindlasti puu.

출력

Väljundi ainsale reale väljastada täisarv $K$ , mis näitab, mitu serva on gaafist $G$ vaja minimaalselt eemaldada, et saada paarismets.

예제2

예제 1
입력
```
4
1 2
2 3
3 4
```
예상 출력
```
1
```
예제 2
입력
```
4
1 2
1 3
1 4
```
예상 출력
```
0
```