solution.md

# BST 插入节点问题

#### 问题描述
给定一棵包含 N 个节点的二叉树，节点编号是 1 ∼ N。其中 i 号节点具有权值 W i ，并且这些节点的权值恰好形成了一棵排序二叉树 (BST)。  
现在给定一个节点编号 K，小明想知道，在这 N 个权值以外，有多少个整数 X (即 X 不等于任何 W i ) 满足：给编号为 K 的节点增加一个权值为 X 的子节点，仍可以得到一棵 BST。  
例如在下图中，括号外的数字表示编号、括号内的数字表示权值。即编号1 ∼ 4 的节点权值依次是 0、10、20、30。

![](https://img-blog.csdnimg.cn/20201010210318917.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01pbGtMZW9uZw==,size_16,color_FFFFFF,t_70#pic_center)

如果 K = 1，那么答案为 0。因为 1 号节点已经有左右子节点，不能再增加子节点了。  
如果 K = 2，那么答案为无穷多。因为任何一个负数都可以作为 2 的左子节点。  
如果 K = 3，那么答案为 9。因为 X = 11,12,··· ,19 都可以作为 3 的左子节点。  

#### 输入格式
第一行包含 2 个整数 N 和 K。  
以下 N 行每行包含 2 个整数，其中第 i 行是编号为 i 的节点的父节点编号P i 和权值 W i 。注意 P i = 0 表示 i 是根节点。  
输入保证是一棵 BST。

#### 输出格式
一个整数代表答案。如果答案是无穷多，输出 −1。  

#### 样例输入
```
4 3
0 10
1 0
1 20
3 30
```
#### 样例输出
```
9
```
#### 评测用例规模与约定
对于 60% 的评测用例，1 ≤ K ≤ N ≤ 100，0 ≤ W i ≤ 200，且 W i 各不相同。  
对于所有评测用例，1 ≤ K ≤ N ≤ 10000，0 ≤ W i ≤ 100000000，且 W i 各不相同。



## aop

### before

```cpp

```

### after

```cpp

```

## 答案

```cpp

```

## 选项

### A

```cpp

```

### B

```cpp

```

### C

```cpp

```