题目简述
一棵 $n$ 个节点的无根树，每个点有一个权值 $s_i$。现要检查 $k$ 个点，当检查完一个点后会选择相邻的一个没有检查过的点进行检查。如果相邻的点都已经检查过那么将会原路返回直到有没有检查过的相邻的点。你可以指定检查的起点，并且在有多个相邻的未检查的点时指定一个点。求被检查的点中最小的权值最大是多少。
$k≤n≤200000,\ s_i≤10^6$
思路
问「最小值最大」，首先很容易可以想到二分。
我们对「检查的点中最小的权值」进行二分，设这个最小权值是 $mid$，我们现在需要解决的问题是在这个最小值的限定条件下最多可以检查几个点 —— 如果点数大于等于 $k$，那么这个最小权值过于小了，否则这个最小权值就有些大了。由于是无根树，我们考虑换根 DP 进行计算。
根据题目的意思可以发现，如果一棵子树上所有的点都满足最小权值的限制，那么我们要优先走这个子树，而对于其他不是所有点都满足最小权值限制的子树，我们只能走一棵 —— 会有一个地方，其所有的没有检查过的相邻节点都小于限定的最小值 —— 所以我们要尽量走最大的那颗。
设 $f_x$ 表示以 $x$ 为根，可以走到的最多的节点是多少；$g_x$ 表示以 $x$ 为根，可以走完的子树的节点是多少。如果有儿子的 $f$ 值等于子树大小，那么显然这个子树一定是可以走完的，所以加入父亲的 $f$ 和 $g$。
否则维护其他子树中可以走到的权值的最大值和次大值。
接着进行换根，用一个 $cnt$ 记录走到当前点为止可以走的最大点数（即当前点上面的点数）。考虑到现在走到节点 $x$ 时：
- 有 「$cnt+x子树大小=整棵树大小$」，以为着此时 $x$ 上面的所有部分都可以走，$f_x,g_x$ 都加上 $cnt$
- 否则，因为现在的 $f_x$ 「子树」的意义包括 $x$ 上面的部分，所以使用 $cnt$ 更新最大值和次大值。
考虑现在走到的点 $x$ 是否符合最小值限制，若符合更新可以走到的最大点数 —— 注意最大值可能已经被更新，所以更新答案时不能使用 $f_x$（因为其里面包括的最大值可能是原来的最大值），而要使用 $g_x+最大值$。
接着考虑如果有 $f_x=x子树大小$，那么也就是说剩下的点都可以走 —— 以 $x$ 子树中任意一点为根和与以 $x$ 为根的答案是相同的，我们已经用以 $x$ 为根的答案更新过一次了，遍历 $x$ 的子树没有意义。
否则遍历 $x$ 的每一个儿子 $y$：
- 若 $x$ 不满足最小值限制，那么此时如果以 $y$ 为根，前面算出来的 $cnt$ 都不能用了，所以 $cnt$ 要清零。
- 否则若 $f_y=x最大值$，那么 $f_y$ 属于 $f_x$ 的一部分，要把这部分减去，同时加上 $x次大值$ 作为 $cnt$
- 否则若 $f_y=y子树大小$，和之前一样，这颗子树都可以走，$f_y$ 属于 $f_x$ 中可以走到底的那部分，不影响最大值
- 否则 $f_y$ 不属于 $f_x$，可以直接使用 $f_x$ 作为 $cnt$
Code
细节比较多，写起来比较麻烦
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<climits>
#include<vector>
#include<queue>
#define int long long
using namespace std;
const int MaxN = 200005;
int n, k, head[MaxN], cntEdge, f[MaxN], g[MaxN], sz[MaxN], s[MaxN];
int fir_mx[MaxN], sec_mx[MaxN], res, ans;
struct Edge{
int destination, nextEdge;
}edge[MaxN*2];
inline void AddEdge(int u, int v){
cntEdge++;
edge[cntEdge].destination = v;
edge[cntEdge].nextEdge = head[u];
head[u] = cntEdge;
return;
}
inline int Read(){
int num = 0, op = 1;
char ch = getchar();
while(!isdigit(ch)){
if(ch == '-') op = -1;
ch = getchar();
}
while(isdigit(ch)){
num = num * 10 + ch - '0';
ch = getchar();
}
return num * op;
}
inline void DFS1(int x, int fa){
sz[x] = 1;
for(int i = head[x]; i; i = edge[i].nextEdge){
int y = edge[i].destination;
if(y == fa) continue;
DFS1(y, x);
sz[x] += sz[y];
}
return;
}
inline void DFS2(int x, int fa, int limit){
f[x] = g[x] = (s[x] >= limit);
fir_mx[x] = sec_mx[x] = 0;
for(int i = head[x]; i; i = edge[i].nextEdge){
int y = edge[i].destination;
if(y == fa) continue;
DFS2(y, x, limit);
if(f[y] == sz[y]){
f[x] += f[y];
g[x] += g[y];
}
else if(s[y] >= limit){
if(f[y] > fir_mx[x]){
sec_mx[x] = fir_mx[x];
fir_mx[x] = f[y];
}
else if(f[y] > sec_mx[x]) sec_mx[x] = f[y];
}
}
f[x] += fir_mx[x];
return;
}
inline void DFS3(int x, int fa, int cnt, int limit){
int tmp = f[x];
if(cnt + sz[x] == n){
g[x] += cnt;
f[x] += cnt;
}
else if(cnt > fir_mx[x]){
sec_mx[x] = fir_mx[x];
fir_mx[x] = cnt;
f[x] += fir_mx[x] - sec_mx[x];
}
else if(cnt > sec_mx[x]) sec_mx[x] = cnt;
if(s[x] >= limit) res = max(res, g[x] + fir_mx[x]);
if(tmp == sz[x]) return;
for(int i = head[x]; i; i = edge[i].nextEdge){
int y = edge[i].destination;
if(y == fa) continue;
if(s[x] < limit){
DFS3(y, x, 0, limit);
continue;
}
if(f[y] == fir_mx[x]) DFS3(y, x, f[x]-fir_mx[x]+sec_mx[x], limit);
else if(f[y] == sz[y]) DFS3(y, x, f[x]-f[y], limit);
else DFS3(y, x, f[x], limit);
}
return;
}
inline bool Judge(int mid){
res = 0;
DFS2(1, 0, mid);
DFS3(1, 0, 0, mid);
return res >= k;
}
signed main(){
n = Read(), k = Read();
for(int i=1; i<=n; i++)
s[i] = Read();
for(int i=1; i<n; i++){
int u = Read(), v = Read();
AddEdge(u, v), AddEdge(v, u);
}
DFS1(1, 0);
int l = 0, r = 1000000;
while(l <= r){
int mid = (l+r) >> 1;
if(Judge(mid)){
ans = mid;
l = mid+1;
}
else r = mid-1;
}
printf("%lld", ans);
return 0;
}