一道蛮简单的DP(然而数据很强,贼容易写挂)
先考虑DFS是如何运作的。假设当前在点,那我们会选择任意一个的儿子,递归搜索的子树,然后再选择一个其他的儿子进行递归搜索。显然,对于任何一个儿子的子树,我们都需要将其全部走完才能走其他儿子的子树。想到这个点这道题就很简单了。
我们二分一个最小值,对于小于这个最小值的点将其打上标记(代表不能走)。设代表对的子树进行DFS,最多能走到多少个点。考虑如何转移状态。我们发现,如果一个子树能走的点的数目等于其子树大小(即),那么我们就可以走完这个子树然后接着走其他子树。否则的话这个子树走到一半我们就必须停止整个过程。
所以转移就是这样:
int buc=0,mx=0;
rep(i,0,side[u].size()-1){//枚举u的儿子
int v=side[u][i];if(v==fa)continue;//v为u的儿子
dfs1(v,u);size[u]+=size[v];
if(down[v]==size[v])buc+=size[v];
else{
mx=max(mx,down[v]);
}
if(!ban[u])down[u]=1+buc+mx;//如果u可以走,他的down值就是能走完的子树大小+不能走完子树里面最大的大小+自己的大小1
}
还有一点小问题就是,这道题的根是可以任意指定的。而我们这个做法是默认1为根的。所以当选择的根不是1时,我们可以记录一个数组,把不在子树内的其他点看作另外一棵子树,就代表了这棵子树进行DFS,最多能走到多少个点,转移方式与数组类似。具体可以看代码。
/*
_|_| _| _| _|
_| _| _| _|_| _|_|_|_| _| _| _|
_| _| _|_| _| _| _|_|
_| _| _| _| _| _| _| _|
_|_| _| _|_|_|_| _|_| _| _|
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
//#define ls (rt<<1)
//#define rs (rt<<1|1)
#define vi vector<int>
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;i++)
#define fi first
#define se second
typedef long long ll;
using namespace std;
const int maxn=202000;
int down[maxn],up[maxn];
int a[maxn],size[maxn];
bool ban[maxn];
vi side[maxn];
multiset<int>q;
void dfs1(int u,int fa){
size[u]=1;int buc=0,mx=0;
rep(i,0,side[u].size()-1){
int v=side[u][i];if(v==fa)continue;
dfs1(v,u);size[u]+=size[v];
if(down[v]==size[v])buc+=size[v];
else{
mx=max(mx,down[v]);
q.insert(down[v]);
}
}
if(!ban[u])down[u]=1+buc+mx;
}
int n,k;
void dfs2(int u,int fa){
q.clear();int buc=0;if(!ban[u])up[u]=max(up[u],1);
rep(i,0,side[u].size()-1){
int v=side[u][i];if(v==fa)continue;
if(down[v]==size[v])buc+=size[v];
else{
q.insert(down[v]);
}
}
if(up[u]==n-size[u]+1)buc+=up[u]-1;
else{
q.insert(up[u]-1);
}
rep(i,0,side[u].size()-1){
int v=side[u][i];if(v==fa)continue;
if(down[v]==size[v])buc-=size[v];
else{
q.erase(q.find(down[v]));
}
if(!ban[u]&&!ban[v]){
up[v]=buc+((q.empty())?0:(*q.rbegin()))+2;
}
if(down[v]==size[v])buc+=size[v];
else{
q.insert(down[v]);
}
}
rep(i,0,side[u].size()-1){
int v=side[u][i];if(v==fa)continue;
dfs2(v,u);
}
}
bool check(int lim){
memset(down,0,sizeof(down));
memset(up,0,sizeof(up));
memset(ban,0,sizeof(ban));
rep(i,1,n)if(a[i]<lim)ban[i]=1;
dfs1(1,0);
dfs2(1,0);
rep(i,1,n){
int ans=0;
if(size[i]==down[i])ans=down[i]+up[i]-1;
else if(up[i]==n-size[i]+1)ans=up[i]+down[i]-1;
else ans=max(up[i],down[i]);
if(ans>=k)return 1;
}
return 0;
}
int main(){
ios::sync_with_stdio(0);
cin>>n>>k;
rep(i,1,n)cin>>a[i];
rep(i,1,n-1){
int u,v;cin>>u>>v;
side[u].pb(v);side[v].pb(u);
}
int l=0,r=1000001;
while(l<r){
int mid=(l+r+1)>>1;
//mid=5;
//cout<<mid<<endl;
if(check(mid))l=mid;
else r=mid-1;
}
cout<<l;
return 0;
}