Infected Tree#11724
You are given a binary tree, which is an acyclic connected undirected graph containing vertices and n - 1 edges. Each vertex has a degree of no more than . The root is the vertex number , with its degree not exceeding .
Unfortunately, the root of the tree is infected. The following process is repeated times:
Huseyn either selects a vertex that is not yet infected (and not yet removed) and removes it along with all its incident edges, or he takes no action.
After that, the infection spreads to every vertex connected by an edge to an already infected vertex (all previously infected vertices remain infected).
Help Huseyn determine the maximum number of vertices he can save from infection (note that removed vertices are not considered saved).
The first line contains the number of vertices in the tree n~(2 \le n \le 3 \cdot 10^5).
Each of the following n - 1 lines contains two integers u_i and v_i~(1 \le u_i, v_i \le n), representing an edge of the tree.
It is guaranteed that the graph is a binary tree with the root at vertex .
Print a single integer — the number of saved vertices.
Example 1
Example 2