この問題は好き。でも時間内には無理。

## E. Preorder Test

### 実装

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
template <class T> bool setmax(T & l, T const & r) { if (not (l < r)) return false; l = r; return true; }
using namespace std;
int main() {
int n, k; cin >> n >> k;
vector<int> a(n); repeat (i,n) cin >> a[i];
vector<vector<int> > g(n);
repeat (i,n-1) {
int u, v; cin >> u >> v; -- u; -- v;
g[u].push_back(v);
g[v].push_back(u);
}
int low  = *min_element(a.begin(), a.end());
int high = *max_element(a.begin(), a.end()) + 1; // [low, high)
while (low + 1 < high) {
int mid = (low + high) / 2;
auto forbidden = [&](int i) { return a[i] < mid; };
bool found = false;
vector<bool> used(n);
vector<int> dp(n);
vector<bool> has_forbidden(n);
repeat (i,n) if (not forbidden(i) and not used[i]) {
int root = -1;
function<void (int)> collect = [&](int i) {
used[i] = true;
for (int j : g[i]) if (not used[j]) {
if (not forbidden(j)) collect(j);
if (forbidden(j)) root = i;
}
};
collect(i);
if (root == -1) {
found = true;
break;
}
function<void (int, int)> dfs = [&](int i, int p) {
if (found) return;
int max_forbidden = 0;
int snd_forbidden = 0;
int sum_free = 0;
for (int j : g[i]) if (j != p) {
if (forbidden(j)) {
has_forbidden[i] = true;
} else {
dfs(j, i);
if (found) return;
if (has_forbidden[j]) {
has_forbidden[i] = true;
setmax(snd_forbidden, dp[j]);
if (max_forbidden < snd_forbidden) swap(max_forbidden, snd_forbidden);
} else {
sum_free += dp[j];
}
}
}
dp[i] = 1 + sum_free + max_forbidden;
if (k <= dp[i] + snd_forbidden) found = true;
};
dfs(root, -1);
if (found) break;
}