P15801 [GESP202603 Level 6] Complete Binary Tree

Related multiple-choice and true/false questions: .

Given a **rooted binary tree** with $n$ nodes, the nodes are numbered $1,2,\dots,n$ in order, and the root node is numbered $1$. For node $i$, its left child is denoted as $l_i$, and its right child is denoted as $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. Please find, among all $n$ subtrees of the given rooted tree, how many of them are complete binary trees.

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 positive integers $l_i, r_i$, representing the index of the left child and the index of the right child of node $i$.

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

For $40\%$ of the test points, $1\leq n\leq 500$ is guaranteed. For all test points, $1\leq n\leq 10^5$ is guaranteed. Translated by ChatGPT 5