P17013 [GESP202606 Level 6] Full Binary Tree

Given a rooted binary tree with $n$ nodes, the nodes are numbered in order as $1, 2, \dots, n$, and the root node is numbered $1$. For node $i$, let the index of its left child be $l_i$, and the index of its right child be $r_i$. In particular, if the left child does not exist then $l_i = 0$, and if the right child does not exist then $r_i = 0$. Each node in the tree corresponds to a subtree rooted at that node. You need to find, among all $n$ subtrees of the given rooted tree, how many of them are full binary trees. A full binary tree means a binary tree where all leaves have the same depth, and every non-leaf node has exactly two children. For example, the following three binary trees are all full binary trees: ``` () () () / \ / \ () () () () / \ / \ () ()() () ``` In the above binary tree with $3$ nodes, there are $3$ subtrees that are full binary trees (including the whole tree itself and all single leaf nodes). Another example: ``` (1) / \ (2) (3) / \ (4) (5) ``` In the above binary tree with $5$ nodes, there are $4$ subtrees that are full binary trees (including the subtree rooted at node $3$, and all single leaf nodes).

The first line contains a positive integer $n$, representing the number of nodes in the rooted binary tree. The next $n$ lines each contain two non-negative integers $l_i, r_i$, representing the indices of the left child and right child of node $i$. The integers are separated by spaces.

Output one line containing one integer, representing the number of full binary trees among all subtrees.

### Constraints For $40\%$ of the test points, it is guaranteed that $1 \le n \le 500$. For all test points, it is guaranteed that $1 \le n \le 10^5$. Translated by ChatGPT 5