e.cpp

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int u, v;
int high, low;
int n, k;
int g_x;
int as[200000];
int ps[200000];
vector<int> es[200000];
vector<int> dp[200000];
vector<int> dp2[200000];

int visit2(int v, int idx) {
    if (dp2[v][idx] >= 0) return dp2[v][idx];

    dp2[v][idx] = 1;
    int u = es[v][idx];
    for (int i=0; i<es[u].size(); i++) {
        if (es[u][i] == v) continue;
        dp2[v][idx] += visit2(u, i);
    }
    return dp2[v][idx];
}

int visit(int v, int idx) {
    if (dp[v][idx] >= 0) return dp[v][idx];
    if (as[v] < g_x) return dp[v][idx] = 0;

    int u = es[v][idx];
    int max_ch = 0;
    dp[v][idx] = 1;
    for (int i=0; i<es[u].size(); i++) {
        if (es[u][i] == v) continue;
        int val = visit(u, i);
        int size = dp2[u][i];

        if (val != size+1) max_ch = max(max_ch, val);
        else dp[v][idx] += val;
    }
    dp[v][idx] += max_ch;
    return dp[v][idx];
}

bool check(int x) {
    g_x = x;
    for (int i=0; i<n; i++) {
        for (int j=0; j<es[i].size(); j++) {
            dp[i][j] = -1;
            dp2[i][j] = -1;
        }
    }

    for (int i=0; i<n; i++) {
        for (int j=0; j<es[i].size(); j++) {
            dp2[i][j] = visit2(i, j);
        }
    }

    for (int i=0; i<n; i++) {
        for (int j=0; j<es[i].size(); j++) {
            dp[i][j] = visit(i, j);
        }
    }

    /*printf("x: %d\n", x);
    for (int i=0; i<n; i++) {
        printf("%d: ", i);
        for (int j=0; j<es[i].size(); j++) {
            printf("%d ", dp2[i][j]);
        }
        puts("");
    }

    for (int i=0; i<n; i++) {
        printf("%d: ", i);
        for (int j=0; j<es[i].size(); j++) {
            printf("%d ", dp[i][j]);
        }
        puts("");
    }*/

    for (int i=0; i<n; i++) {
        for (int j=0; j<es[i].size(); j++) {
            if (dp[i][j] >= k) return true;
        }
    }
    return false;
}

int main() {
    scanf("%d%d", &n, &k);
    for (int i=0; i<n; i++) {
        scanf("%d", &as[i]);
        ps[i] = as[i];
    }
    sort(ps, ps+n);

    for (int i=0; i<n-1; i++) {
        scanf("%d%d", &u, &v);
        --u;
        --v;
        es[u].push_back(v);
        es[v].push_back(u);
    }
    for (int i=0; i<n; i++) {
        dp[i].resize(es[i].size());
        dp2[i].resize(es[i].size());
    }

    low = -1;
    high = n;
    while (high - low > 1) {
        int mid = (high+low)/2;
        if (check(ps[mid])) low = mid;
        else high = mid;
    }
    printf("%d\n", ps[low]);
}