题号：NC21206
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
题目描述
msc有n个小宠物，这些宠物的家是连在一起的，更有趣的是，这些宠物的家之间的连接关系形成了一个树的形态。
每个小宠物的习性是不太一样的，比如说有的可能吃素，有的可能吃荤。
作为直觉系女生，msc凭着自己突出的直觉对每个小宠物都有一个关于习性的评估值，对于宠物i，它的评估值是a[i]。
考虑到习性差异过大会很难伺候，甚至宠物间会发生冲突，所以msc希望去掉至多k个连接关系使得任意两个可以互相到达的宠物间的评估值的差的最大值尽量小。
两个宠物(x,y)可以互相到达当且仅当存在一个序列s1,s2,...,sk-1,sk使得对于1 ≤ i < k，si与si+1之间相连且s1=x,sk=y
现在msc给出了n个小宠物的评估值a[1..n]和这棵树的形态，msc希望你帮她求出去掉至多k个连接关系之后，任意两个可以互相到达的宠物间的评估值的差的最大值最小是多少。
每个小宠物的习性是不太一样的，比如说有的可能吃素，有的可能吃荤。
作为直觉系女生，msc凭着自己突出的直觉对每个小宠物都有一个关于习性的评估值，对于宠物i，它的评估值是a[i]。
考虑到习性差异过大会很难伺候，甚至宠物间会发生冲突，所以msc希望去掉至多k个连接关系使得任意两个可以互相到达的宠物间的评估值的差的最大值尽量小。
两个宠物(x,y)可以互相到达当且仅当存在一个序列s1,s2,...,sk-1,sk使得对于1 ≤ i < k，si与si+1之间相连且s1=x,sk=y
现在msc给出了n个小宠物的评估值a[1..n]和这棵树的形态，msc希望你帮她求出去掉至多k个连接关系之后，任意两个可以互相到达的宠物间的评估值的差的最大值最小是多少。
输入描述:
第一行两个整数n和k，表示宠物的数量和至多去掉的连接关系数量。
第二行n个整数a[i]，第i个数表示宠物i的评估值。
接下来n-1行，每行两个正整数u,v，表示宠物u和宠物v的家之间有连接关系。
输出描述:
一样一个整数，表示去掉至多k个连接关系之后，任意两个可以互相到达的宠物间的评估值的差的最大值最小是多少。
示例1
备注:
|a[i]|≤1000000000
1≤k+1≤n≤1000