| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 512 MB | 5 | 5 | 4 | 100.000% |
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.
4 1 2 2 3 3 4
1
4 1 2 1 3 1 4
0