玄关求条

#include<iostream>
#include<vector>
using namespace std;
const int N=3e5+10,INF=2e9;
int a[N];
vector<int> e[N];
int f[N];  //i子树中距离i最远的未被覆盖的节点到i有多远。若为负数，其绝对值为i与最近的关键点的距离
int cnt;  //当前需要的关键点个数
void dfs(int u,int fa,int x){
    if(e[u].size()==1&&u!=1){f[u]=1;return;}  //叶子
    f[u]=-INF;
    int minn=INF;
    for(int v:e[u]){
        if(v==fa) continue;
        dfs(v,u,x);
        f[u]=max(f[u],f[v]);
        minn=min(minn,f[v]);
    }
    f[u]++;  //算上自己
    if(f[u]<=-minn) f[u]=minn+1;
    else if(f[u]>x) f[u]=-x,cnt++;
    if(u==1&&f[u]>0) cnt++;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1,x,y;i<n;i++) cin>>x>>y,e[x].push_back(y),e[y].push_back(x);
    int l=0,r=n,ans=0;
    while(l<=r){  //二分最远距离/最大时间
        int mid=(l+r)>>1;
        cnt=0;dfs(1,0,mid);
        if(cnt<=k) ans=mid,r=mid-1;
        else l=mid+1;
    }
    cout<<ans;
    return 0;
}