```cpp
#include <bits/stdc++.h>
const int N = 2e5 + 5;
using namespace std;
int n , a[N] , k , b[N];
struct edge {
int to , nxt;
}e[N << 1];
int head[N] , cnt = 1;
void adde(int u , int v){
e[ ++ cnt] = {v , head[u]};
head[u] = cnt;
e[ ++ cnt] = {u , head[v]};
head[v] = cnt;
}
int f[N] , siz[N] , g[N];
void dfs(int u , int fa){
siz[u] = 1;
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == fa) continue;
dfs(v , u);
siz[u] += siz[v];
}
if(b[u] == 0) return ;
int maxx = 0;
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == fa || b[v] == 0) continue;
if(siz[v] == f[v]){
f[u] += f[v];
}
else {
maxx = max(maxx , f[v]);
}
}
f[u] += maxx , g[u] = maxx;
}
int ans = 0;
void ch_rt(int u , int fa){
ans = max(ans , max(b[u] , f[u]));
// cout << u << " " << f[u] << " " << g[u] << " " << siz[u] << endl;
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == fa) continue;
int rf = f[v] , rg = g[v] , rs = siz[v];
if(b[v] && b[u]){
if(siz[u] - siz[v] == f[u] - f[v]){
f[v] += siz[u] - siz[v];
}
else {
int tmp = f[u] - f[v];
if(tmp > g[v]){
f[v] = f[v] - g[v] + tmp;
g[v] = tmp;
}
}
}
siz[v] = siz[u];
ch_rt(v , u);
f[v] = rf , g[v] = rg , siz[v] = rs;
}
}
bool check(int x){
memset(g , 0 , sizeof g);
memset(siz , 0 , sizeof siz);
for(int i = 1; i <= n; ++ i){
b[i] = f[i] = (a[i] >= x);
// cout << f[i] << " ";
}
// cout << endl;
// cout << x << endl;
dfs(1 , 0);
// for(int i = 1; i <= n; ++ i){
// cout << f[i] << " ";
// }cout << endl;
ans = 0;
ch_rt(1 , 0);
return (ans >= k);
}
int main(){
cin >> n >> k;
int minx = 2e9 , maxx = -1;
for(int i = 1; i <= n; ++ i){
cin >> a[i];
maxx = max(maxx , a[i]);
minx = min(minx , a[i]);
}
for(int i = 1; i < n; ++ i){
int u , v;
cin >> u >> v;
adde(u , v);
}
int l = minx , r = maxx , res = -1;
while(l <= r){
int mid = (l + r) / 2;
if(check(mid)){
res = mid;
l = mid + 1;
}
else {
r = mid - 1;
}
}
// check(5);
cout << res;
return 0;
}
```
by NightDiver @ 2024-03-27 15:55:24
试过了并不是这道题目常见的 **从权值最小节点开始换根** 的问题
by NightDiver @ 2024-03-27 16:20:25
@[NightDiver](/user/985711) 你的换根没有记次小值。
形式化地来说，根从 $u$ 变化到 $v$ 时，需要计算 $u$ 作为 $v$ 的儿子时的 DP 值 $tmp$：
1. $siz[v]=f[v]$，此时 $v$ 对 $u$ 的贡献是 $f[v]$，直接 $f[u]-f[v]$。
2. $f[v]$ 是 $u$ 子树内最大值，此时是 $f[u]-g[u]+h[u]$。
3. $f[v]$ 不是最大值，此时就是 $f[u]$。
其中 $g[u]$ 和 $h[u]$ 分别表示 $u$ 子树内最小值和次小值，就不放代码了。
另外换根后 $siz[u]=n$，并且不用还原数组，简化了一下代码。
```cpp
void ch_rt(int u , int fa){
ans = max(ans , max(b[u] , f[u]));
// cout << u << " " << f[u] << " " << g[u] << " " << siz[u] << endl;
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == fa) continue;
if(b[v] && b[u]){
int tmp = f[u] - (f[v]==siz[v]?f[v]:f[v]==g[u]?g[u]-h[u]:0);
if(n - siz[v] == tmp){
f[v] += tmp;
}
else {
if(tmp > g[v]){
f[v] = f[v] - g[v] + tmp;
h[v]=g[v],g[v] = tmp;
}else if(tmp > h[v]){
h[v] = tmp;
}
}
}
ch_rt(v , u);
}
}
```
by Kazemaru @ 2024-03-27 17:57:22
@[Kazemaru](/user/218376) 谢谢
by NightDiver @ 2024-03-27 18:23:30
@[Kazemaru](/user/218376) 关注了
by NightDiver @ 2024-03-27 18:34:21
@[Kazemaru](/user/218376) 太妙了，一种不一样的考虑换根DP的思路
by NightDiver @ 2024-03-27 20:20:05