Score : $600$ points
Given is a tree with $N$ vertices. The vertices are numbered $1,2,\ldots,N$, and the $i$-th edge $(1 \leq i \leq N-1)$ connects Vertex $u_i$ and Vertex $v_i$.
Find the number of integers $i$ $(1 \leq i \leq N)$ that satisfy the following condition.
Input is given from Standard Input in the following format:
$N$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_{N-1}$ $v_{N-1}$
Print the answer.
3 1 2 2 3
2
The size of the maximum matching of the original tree is $1$.
The size of the maximum matching of the graph obtained by deleting Vertex $1$ and all incident edges from the tree is $1$.
The size of the maximum matching of the graph obtained by deleting Vertex $2$ and all incident edges from the tree is $0$.
The size of the maximum matching of the graph obtained by deleting Vertex $3$ and all incident edges from the tree is $1$.
Thus, two integers $i=1,3$ satisfy the condition, so we should print $2$.
2 1 2
0
6 2 5 3 5 1 4 4 5 4 6
4