Skip to content

Instantly share code, notes, and snippets.

@potetisensei
Created February 28, 2016 20:31
Show Gist options
  • Save potetisensei/b18c56faa5753038e581 to your computer and use it in GitHub Desktop.
Save potetisensei/b18c56faa5753038e581 to your computer and use it in GitHub Desktop.
#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]);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment