Even Forest

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

요약

트리에서 간선을 최소한으로 제거해 남은 각 성분에서 두 리프 사이의 홀수 길이 경로가 없도록 만든다.

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

문제

An undirected tree is called even if there is no simple path of odd length connecting two of its leaves. In particular, a tree with just one vertex is considered even.

You are given an undirected tree $G$ with vertices numbered from $1$ to $n$ . A graph obtained by removing some (possibly none) of the edges of $G$ is called a forest: it consists of one or more disjoint trees. Determine the minimum possible number $k$ such that we can remove $k$ edges of $G$ in such a way that the resulting forest consists only of even trees.

입력

The first line contains one integer $n$ ( $1 \le n \le 10^6$ ).

Each of the next $n - 1$ lines contains two integers $u\_i$ and $v\_i$ ( $1 \le u\_i, v\_i \le n$ ) denoting an edge connecting vertex $u\_i$ and vertex $v\_i$ .

The graph is guaranteed to be a tree.

출력

Output the minimum number of edges $k$ such that we can remove $k$ edges of $G$ in such a way that each tree in the resulting forest is even.

예제2

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