P3523 [POI 2011] DYN-Dynamite

首先二分，问题转换成每个被选中点可以标记距离祂 \(mid\) 以内的点，求最少需要选几个点。
考虑从深到浅贪心，对于每一个关键点，如果祂现在没被标记，最优的方案为选祂的 \(mid\) 级祖先，然后标记祂的 \(mid\) 级祖先的 \(mid\) 级邻域。标记直接暴力跑，记录一下每个点被标记时最多还剩多少步，复杂度是假的，但能过

代码

#include<bits/stdc++.h>
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T&x){
        x=0;char c=getchar();bool f=0;
        while(!isdigit(c)) c=='-'?f=1:0,c=getchar();
        while(isdigit(c)) x=x*10+c-'0',c=getchar();
        f?x=-x:0;
    }
    template<typename T>
    inline void write(T x){
        if(x==0){putchar('0');return ;}
        x<0?x=-x,putchar('-'):0;short st[50],top=0;
        while(x) st[++top]=x%10,x/=10;
        while(top) putchar(st[top--]+'0');
    }
    inline void read(char&c){c=getchar();while(isspace(c)) c=getchar();}
    inline void write(char c){putchar(c);}
    inline void read(string&s){s.clear();char c;read(c);while(!isspace(c)&&~c) s+=c,c=getchar();}
    inline void write(string s){for(int i=0,len=s.size();i<len;i++) putchar(s[i]);}
    template<typename T>inline void write(T*x){while(*x) putchar(*(x++));}
    template<typename T,typename...T2> inline void read(T&x,T2&...y){read(x),read(y...);}
    template<typename T,typename...T2> inline void write(const T x,const T2...y){write(x),putchar(' '),write(y...),sizeof...(y)==1?putchar('\n'):0;}
}using namespace IO;
const int maxn=300010;
template<int maxn,int maxm>class LSQXX{
public:
    int head[maxn],nxt[maxm*2],to[maxm*2],cnt=1;
    void add(int u,int v){nxt[++cnt]=head[u],to[cnt]=v,head[u]=cnt;}
};
LSQXX<maxn,maxn*2>e;
int n,m,d[maxn],ans,sy[maxn],deep[maxn],cnt,fa[maxn],now,mx_bs[maxn];
struct node{
    int d,z;
    bool operator<(const node t)const{return z<t.z;}
    bool operator>(const node t)const{return z>t.z;}
}a[maxn];
void dfs(int u,int fa=0){
    deep[u]=deep[fa]+1;
    ::fa[u]=fa;
    for(int i=e.head[u];i;i=e.nxt[i]){
        int v=e.to[i];
        if(v==fa) continue;
        dfs(v,u);
    }
}
bool flag[maxn];
void bj(int u,int bs,int lt=0){
    flag[u]=1;if(bs==0) return ;
    if(mx_bs[u]>=bs) return ;
    mx_bs[u]=bs;
    for(int i=e.head[u];i;i=e.nxt[i]){
        int v=e.to[i];
        bj(v,bs-1,u);
    }
}
bool check(int x){
    memset(flag,0,sizeof(flag));
    memset(mx_bs,0,sizeof(mx_bs));
    int g=0;
    for(int i=1;i<=cnt;i++){
        if(flag[a[i].d]) continue;
        g++;
        int u=a[i].d;
        for(int j=1;j<=x;j++){
            if(fa[u]) u=fa[u];
            else break;
        }
        bj(u,x);
    }
    return g<=m;
}
signed main(){
    read(n,m);
    for(int i=1;i<=n;i++){
        read(d[i]);
        if(d[i]) a[++cnt]={i,0};
    }
    for(int i=1;i<n;i++){
        int u,v;read(u,v);
        e.add(u,v),e.add(v,u);
    }
    dfs(1);
    for(int i=1;i<=cnt;i++) a[i].z=deep[a[i].d];
    sort(a+1,a+1+cnt,greater<node>());
    int l=0,r=n,ans=n;
    while(l<=r){
        int mid=l+r>>1;
        if(check(mid)) r=mid-1,ans=mid;
        else l=mid+1;
    }
    write(ans);
    return 0;
}