logo AlgoBeat OnlineJudge
登录 注册

#215858. [GESP202603 六级] 完全二叉树

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

对应的选择、判断题:https://ti.luogu.com.cn/problemset/1210


给定一棵包含 个结点的有根二叉树,结点依次以 编号,根结点编号为

对于结点 ,其左儿子的编号记为 ,右儿子编号记为 。特别地,如果左儿子不存在则 ,如果右儿子不存在则

树中每个结点都对应一棵以其为根的子树。请你求出给定有根树的所有 棵子树中,有多少棵子树是完全二叉树。

输入格式

第一行,一个正整数 ,表示有根二叉树结点数量。

接下来 行,每行两个正整数 ,表示结点 的左儿子编号和右儿子编号。

输出格式

输出一行,一个整数,表示所有子树中完全二叉树的数量。

样例

样例输入 1

4
2 3
4 0
0 0
0 0

样例输出 1

4

样例输入 2

4
2 3
0 0
4 0
0 0

样例输出 2

3

数据范围与提示

对于 的测试点,保证

对于所有测试点,保证