该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给出一个 $n$ 个点，以 $1$ 为根的二叉树，其中每个点有个权值。有 $q$ 次修改，每次修改一个点的点权，你需要在每次修改之后输出有多少个点 $u$ ，满足以 $u$ 为根的子树是一棵二叉搜索树。

一棵树是二叉搜索树当且仅当对所有点 $x$ 均满足以下两个条件：

• 不存在左子树或左子树中的所有点的点权都 $\le x$的点权
• 不存在右子树或右子树中的所有点的点权都 $\ge x$ 的点权

输入格式

第一行两个正整数 $n,q$ 。

接下来 $n$ 行，第 $i+1$ 行两个数 $l_i,r_i$，代表点 $i$ 的左儿子和右儿子的标号，如果不存在则为 $0$ 。

接下来一行 $n$ 个数 $v_1,v_2,⋯,v_n$，代表 $n$ 个点初始的点权。

接下来 $q$ 行每行两个数 $k_i,x_i$ ，代表这次修改将点 $k_i$ 的权值改为 $x_i$ 。

输出格式

一共 $q$ 行，每行包含一个正整数，第 $i$ 行的正整数代表第 $i$ 次修改之后的答案。

样例输入 1

6 5
2 3
4 0
5 6
0 0
0 0
0 0
4 1 3 2 2 5
3 3
2 2
3 5
5 4
6 1

样例输出 1

4
5
5
6
4

样例输入 2

8 10
4 5
8 0
0 0
3 7
0 6
0 0
2 0
0 0
7 0 9 3 6 0 6 2
3 0
4 0
8 2
2 3
7 6
1 6
5 7
6 9
1 1
1 7

样例输出 2

3
3
3
6
6
6
6
8
7
8

数据范围

对于$10\%$ 的数据，$n,q\le500$。

对于 $20\%$ 的数据，$n,q\le 5000$。

对于另外 $30\%$ 的数据，保证固定点数后，树的构造方式为：以 $1$ 为根，在 $[0, 当前子树需要的大小 −1]$ 中均匀随机，并其设为左子树的大小，递归到左子树和右子树继续构造。

对于$100\%$ 的数据，$1\le n,q\le2*10^5,0\le l_i,r_i\le n,1\le k_i\le n,0\le v_i,x_i\le 10^9$​。