P1922 Maid Cafe and Board Game Bar

Xiao V (小 v) takes his cute little sister out to play. The sister wants to go to a maid cafe, while Xiao V wants to go to a board game bar. Sister: "I’ll ask you a question. If you get it wrong, you’ll be my slave for a day. If you get it right, I’ll listen to you for the whole day." Xiao V: "You’ll listen to me for everything!?" Sister: "Heehee, you’d better just answer the question!" To secure a happy day for himself, Xiao V comes to you for help.

Xiao V’s world is organized as a tree. At each node, you may build a maid cafe, a board game bar, or leave it empty. After fixing node $1$ as the root, the planning bureau requires: for every non-leaf node $i$, let $cafe_i$ be the number of maid cafes and $table_i$ be the number of board game bars in its subtree (including itself). It must hold that $cafe_i = table_i$. The sister’s question is: what is the maximum number of maid cafes that can be placed on this tree?

The first line contains a positive integer $n$, the number of nodes in the world. Lines $2$ through $n$ each contain two positive integers $u$, $v$, indicating that there is an edge between $u$ and $v$.

Output a single line with the maximum possible number of maid cafes.

Constraints - For $30\%$ of the testdata, it is guaranteed that $n \le 20$. - For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 10^5$, $1 \le u, v \le n$. Translated by ChatGPT 5