1-E：疫情

class Solution:
    def minValueofh(self, n, m, line, array):
        from collections import defaultdict
        dic = defaultdict(list)
        for a, b in array:
            dic[a].append(b)
            dic[b].append(a)
        for i in range(m, 0, -1):
            if not self.check(i, line, dic):
                continue
            else:
                return self.check(i, line, dic)
        return -1
    def check(self, i, line, dic):
        leaf = []
        father = {}
        k = 1
        for f, s in dic.items():
            if len(s) == 1:
                leaf.append(f)
            else:
                father[f] = len(s)
                flag = max(line) + 1
            while flag > 0:
                for f, s in dic.items():
                    if line[f-1] >= flag:
                        if f in leaf:
                            k += 1
                        else:
                            k += father[f]
                    else:
                        continue
                if i == k:
                    return flag
                flag -= 1
            return 0
if __name__ == "__main__":
    [n, m] = list(map(int, input().split()))
    line = list(map(int, input().split()))
    array = []
    for _ in range(n-1):
        lists = list(map(int, input().split()))
        array.append(lists)
    s = Solution()
    ans = s.minValueofh(n, m, line, array)
    print(ans)

//并查集+二分
//已通过全部用例
//二分查找h的最小值。将所有小于h的城市按照原树中结构相连（使用并查集），并统计当前h下的连通块数量。
#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
typedef long long ll;

int Find(vector<int>& parent, int index){
    if(parent[index] != index){
        parent[index] = Find(parent, parent[index]);
    }
    return parent[index];
}

void Union(vector<int>& parent, int index1, int index2){
    parent[Find(parent, index1)] = Find(parent, index2);
}

int cal(unordered_set<int> sp, vector<int>& parent, vector<pair<int, int>>& b){
    for(int i = 0; i < b.size(); i++){
        int x = b[i].first, y = b[i].second;
        if(!sp.count(x) && !sp.count(y)){
            Union(parent, x, y);
        }
    }
    unordered_set<int> count;
    for(int i = 1; i < parent.size(); i++){
        count.insert(Find(parent, i));
    }
    return count.size();
}
int main(){
    int n, m;
    cin>>n>>m;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin>>a[i];
    vector<pair<int, int>> b(n - 1);
    for(int i = 0; i < n - 1; i++) cin>>b[i].first>>b[i].second;
    vector<int> parent(n + 1, 0);
    for(int i = 1; i <= n; i++) parent[i] = i;
    if(n == m) cout<<-1;
    else{
        int l = 0, r = *max_element(a.begin(), a.end()) + 1;
        while(l < r){
            int mid = (l + r) >> 1;
          
            unordered_set<int> sp;
            for(int i = 0; i < n; i++){
                if(a[i] >= mid) sp.insert(i + 1);
            }
            vector<int> p = parent;
            int now = cal(sp, p, b);
          //  cout<<l<<' '<<r<<' '<<now<<endl;
            if(now <= m) r = mid;
            else l = mid + 1;
        }
        cout<<r;
    }
}

#解法：并查集，先按题目给的城市关系集合进行连接，
#根据城市人口密度从大到小进行排序然后从开始剔除密度最高的城市进而更新城市关系集合再次重构并查集，
#直到连通数大于m，记录每次更新的城市中密度最高的然后加1形成一个每个连通数对应的h值列表，
#表中的最小值即是答案
#题目给的测试数据不符合题目给的输入要求所以我只测了示例，
class UnionFind(object):
    def __init__(self, n):
        """长度为n的并查集"""
        self.uf = [-1 for i in range(n + 1)]  # 列表0位置空出
        self.sets_count = n  # 判断并查集里共有几个集合, 初始化默认互相独立

    def find(self, p):
        """尾递归"""
        if self.uf[p] < 0:
            return p
        self.uf[p] = self.find(self.uf[p])
        return self.uf[p]

    def union(self, p, q):
        """连通p,q 让q指向p"""
        proot = self.find(p)
        qroot = self.find(q)
        if proot == qroot:
            return
        elif self.uf[proot] > self.uf[qroot]:  # 负数比较, 左边规模更小
            self.uf[qroot] += self.uf[proot]
            self.uf[proot] = qroot
        else:
            self.uf[proot] += self.uf[qroot]  # 规模相加
            self.uf[qroot] = proot
        self.sets_count -= 1  # 连通后集合总数减一

    def is_connected(self, p, q):
        """判断pq是否已经连通"""
        return self.find(p) == self.find(q)  # 即判断两个结点是否是属于同一个祖先

n, m = map(int, input().split(' '))
if n <= m:
    print(-1)
else:
    r = list(map(int, input().split(' ')))
    rate = []
    for i in range(1, n + 1):
        rate.append((i, r[i - 1]))
    relation = []
    del_rel = []
    uf = UnionFind(n)
    for i in range(n - 1):
        a, b = map(int, input().split(' '))
        relation.append((a, b))
        uf.union(a, b)
    h = []
    while uf.sets_count <= m:
        print(uf.sets_count)
        item = max(rate, key=lambda x: x[1])
        # print("item:{}".format(item))
        rate.remove(item)
        # print("rate:{}".format(rate))
        h.append(item[1] + 1)
        for i in range(len(relation) - 1, -1, -1):
            if relation[i][0] == item[0]:
                relation.remove(relation[i])
            elif relation[i][1] == item[0]:
                relation.remove(relation[i])
        # print("relation:{}".format(relation))
        uf = UnionFind(n)
        for ra in relation:
            uf.union(ra[0], ra[1])
        # print(uf.sets_count)
    print(min(h))