Background

Related multiple-choice and true/false questions: https://ti.luogu.com.cn/problemset/1210.

Problem Description

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.

Input Format

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 Format

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

4
2 3
4 0
0 0
0 0

4

4
2 3
0 0
4 0
0 0

3

Hint

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