You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时空限制

2S/512M

题目描述

给定一棵由 $n$ 个节点组成的有根树，节点的编号从 $1$ 到 $n$，根节点的编号为 $1$。

节点 $i$ 的权值为 $a_i$。定义一条路径的宽度为路径上所有节点（包括路径的两端）的最大权值减最小权值。

现在要在节点间架设线路，如果节点 $y$ 在以节点 $x$ 为根的子树中，且节点 $x$ 到节点 $y$ 的路径的宽度不超过线路的宽度，才可以架设节点 $x$ 到 节点 $y$ 的线路。

如果架设了节点 $x$ 到 节点 $y$ 的线路，那么节点 $x$ 到节点 $y$ 的路径上的点都在这条线路上。

有 $q$ 个查询，第 $i$ 个查询求如果线路宽度为 $w_i$，至少要架设多少条线路才能令每个节点都在至少一条线路上。

格式

输入格式

第一行包含两个整数 $n,q$，分别表示节点的数量和查询的数量。

第二行包含 $n$ 个整数 $a_i$，分别表示每个节点的权值。

接下来 $n-1$ 行每行包含两个整数 $u_i,v_i$，表示在节点 $u_i$ 和节点 $v_i$ 之间有一条边。

接下来 $q$ 行每行一个整数 $w_i$，表示一个查询。

输出格式

对于每个查询，在单独的一行中输出一个整数，表示线路宽度为 $w_i$ 时至少要架设多少条线路才能令每个节点都在至少一条线路上。

样例

样例输入 #1

5 4
4 9 7 1 10 
2 3
4 1
1 3
5 1
4
2
1
10

样例输出 #1

3
4
5
3

样例解释 #1

对于第 $1$ 个询问，一种线路架设方案为：①节点 $1$ 到节点 $4$、②节点 $3$ 到节点 $2$、③节点 $5$ 到节点 $5$。

对于第 $2$ 个询问，一种线路架设方案为：①节点 $1$ 到节点 $1$、②节点 $3$ 到节点 $2$、③节点 $4$ 到节点 $4$、④节点 $5$ 到节点 $5$。

对于第 $3$ 个询问，一种线路架设方案为：①节点 $1$ 到节点 $1$、②节点 $2$ 到节点 $2$、③节点 $3$ 到节点 $3$、④节点 $4$ 到节点 $4$、⑤节点 $5$ 到节点 $5$。

对于第 $4$ 个询问，一种线路架设方案为：①节点 $1$ 到节点 $2$、②节点 $1$ 到节点 $4$、③节点 $1$ 到节点 $5$。

数据规模

对于 $50\%$ 的数据，$n\leq 1000$。

另有 $35\%$ 的数据，$q\leq 2$。

对于 $100\%$ 的数据，$1\leq n\leq 10^5$，$1\leq q\leq 20$，$1\leq a_i\leq 10^9$，$1\leq u_i,v_i\leq n$，$1\leq w_i\leq 10^9$。