到了 Vianu 年度服务器维护的时间了。有些维护工作可以由人工完成，但连接网络的电缆穿过了一系列地下管道，这些管道太小了，无法进入！幸运的是，一位聪明的工程师想出了一个主意，让训练有素的老鼠来检查计算机。

每只老鼠可以从一台计算机进入网络，沿着地下管道中的电缆移动，并从另一台计算机离开，沿途检查所有计算机。因为老鼠非常懒惰，每只老鼠在感到疲倦之前，只会沿着其入口和出口之间的一条简单路径移动。

维护人员希望让老鼠检查一些计算机，使得在剩余未检查的计算机中，安全代码的配置“足够平衡”。你的任务是确定所需的最少老鼠数量。

有 $N$ 台计算机，编号为 $0$ 到 $N - 1$，通过 $N - 1$ 条电缆连接。该网络是一棵树（连通且无环）。

一只老鼠可以检查其进入网络的计算机与离开网络的计算机之间的唯一简单路径上的每台计算机。正式地，如果一只老鼠在计算机 $S$ 进入并在计算机 $T$ 离开（$S, T \in \{0, \dots, N - 1\}$），那么这只老鼠将检查所有满足以下条件的计算机 $v_1, v_2, \dots, v_k$：

• $v_1 = S$ 且 $v_k = T$，
• 对于所有 $1 \le i < k$，计算机 $v_i$ 和 $v_{i+1}$ 直接由电缆连接，
• $k$ 是最小的。

老鼠可以重复使用相同的电缆和计算机，且一台计算机可以被多只老鼠检查。

每台计算机 $i \in \{0, \dots, N - 1\}$ 都有一个关联的正整数代码 $C_i \ge 1$。维护人员确定了一个最大可接受差值 $D$。在所有老鼠完成工作后，令剩余未检查的计算机集合为 $R \subseteq \{0, \dots, N - 1\}$。维护人员希望确保对于任意一对 $i, j \in R$，都有 $|C_i - C_j| \le D$。

换句话说，剩余计算机中最大代码与最小代码之差必须至多为 $D$。

每只老鼠在疲倦前只能检查一条路径。你希望最小化所使用的老鼠数量。

实现细节

你需要实现以下函数：

int solve(int N, int D, std::vector<int> C, std::vector<int> P, std::vector<int> Q)

该函数接收以下参数：

• $N$：计算机的数量。
• $D$：最大可接受差值。
• $C$：计算机的代码。
• $P$ 和 $Q$：两个长度为 $N - 1$ 的向量，表示对于所有 $0 \le i < N - 1$，计算机 $P_i$ 和 $Q_i$ 之间有一条电缆。

该函数应返回所需的最少老鼠数量，使得在所有老鼠检查完它们的路径后，剩余未检查的计算机满足：

$$\max_{i \in R} C_i - \min_{i \in R} C_i \le D$$

数据范围

• $1 \le N \le 200\,000$。
• 对于所有 $0 \le i \le N - 1$，$1 \le C_i \le 1\,000\,000\,000$。
• $1 \le D \le 1\,000\,000\,000$。
• $0 \le p_i, q_i < N$，$p_i \ne q_i$，且所有无序对 $(p_i, q_i)$ 互不相同。

子任务

样例

样例输入 1

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

样例输出 1

1

样例输入 2

20 30
13 36 11 35 4 9 42 9 1 4 11 3 15 31 46 41 31 17 11 12
19 5
19 0
19 13
19 9
19 4
19 10
5 1
19 18
0 7
5 8
19 12
5 17
13 16
5 14
13 3
19 6
5 15
5 2
4 11

样例输出 2

3

说明

在第一个样例中，有 $N = 5$ 台计算机且 $D = 3$。网络结构如下图所示：

一种可能的策略是派出一只老鼠，其路径起点为计算机 $0$，终点为计算机 $3$，沿途经过路径 $0 - 1 - 2 - 3$。在检查完该路径后，网络是安全的。