Dotcpp  >  编程题库  >  蓝桥杯2020年第十一届省赛真题-BST插入节点问题
题目 2588:

蓝桥杯2020年第十一届省赛真题-BST插入节点问题

时间限制: 2s 内存限制: 192MB 提交: 431 解决: 32

题目描述

此题已加强,卡了 的解法。如果数据有误请联系管理员。

给定 个结点的一颗二叉搜索树,结点编号 。每个结点 有一整数点权 。给定一整数 ,问有多少个整数 使得 插入这棵二叉搜索树后是结点 的子结点。

保证 不重复, 不能和 重复。

输入格式

第一行两个整数
接下来 行,每行两个整数 ,表示结点 的父结点编号为 ,结点 点权为

输出格式

输出一个整数,表示 的个数。如果 可取无限多个,则输出 1 。

样例输入

4 3
0 10
1 0
1 20
3 30

样例输出

9

提示

数据范围

对于 60% 的数据,
对于 100% 的数据,

样例解释

0102030

如果 ,那么答案为 0 。因为 1 号结点已经有左右子结点,不能再增加子结点了。

如果 ,那么答案为无穷大。因为任何一个负数都可以作为 2 的左子结点。

如果 ,那么答案为 9 。因为 都可以作为 3 的左子结点。

标签