Byteotian Cave的结构是一棵N个节点的树,其中某些点上面已经安置了烟火,现在需要点燃M个点上的引线引爆所
有的烟火。某个点上的引线被点燃后的1单位时间内,在树上和它相邻的点的引线会被点燃。如果一个有烟火的点
的引信被点燃,那么这个点上的烟火会爆炸。求引爆所有烟火的最短时间。
1<=m<=n<=300000

Sample Input
7 2
1 0 1 1 0 1 1
1 3
2 3
3 4
4 5
5 6
5 7
Sample Output
1

可以发现实际上要求的就是选择点到所有烟火点的最大距离最小,这个可以二分答案,然后我就不会做了
一个说法是:如果选择的代价相等那么就是贪心,如果选择代价不等那么就是dp

二分最短时间,求出最小的需要引爆数
至于关键点的引爆状态有关
f[i] 以i为根的子树中已经引爆的点离i最近的距离
g[i] 以i为根的子树中未引爆的点离i最远的距离
回溯到每个节点时,优先考虑用另一个儿子中的点覆盖其他儿子
if(f[i]+g[i]<=mid) g[i]=INF
if(g[i]==mid) 必须引爆x

#include <iostream>
#include <cstdio>
#include <cstring>
#define  INF 1000000000
#define maxn 300005
using namespace std;
int n,m;
int a[maxn];
int ans;
struct edge
{
    int to,ne;
}b[maxn*2];
int k=0,head[maxn];
int f[maxn],g[maxn];
int limit;
int num=0,op1=0;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}
void add(int u,int v)
{
    k++;
    b[k].to=v; b[k].ne=head[u]; head[u]=k;
}
void dfs(int x,int pre)
{
    f[x]=INF;
    if(a[x]) g[x]=0;
    else g[x]=-INF;
    for(int i=head[x];i!=-1;i=b[i].ne)
    if(b[i].to!=pre)
    {
        dfs(b[i].to,x);
        f[x]=min(f[x],f[b[i].to]+1);
        g[x]=max(g[x],g[b[i].to]+1);
    }
    if(g[x]+f[x]<=limit)  g[x]=-INF;
    if(g[x]==limit){
        f[x]=0,g[x]=-INF,num++;
    }
}
bool check(int x)
{
    if(!x) return op1<=m;
    limit=x; num=0;
    dfs(1,0);
    if(g[1]+f[1]>limit) num++;
    return num<=m;
}
void getans()
{
    int l=0,r=n,mid;
    ans=n;
    while(l<=r){
        mid=(l+r)>>1;
        if(check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
}
int main()
{
    memset(head,-1,sizeof(head));
    n=read(); m=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        if(a[i]) op1++;
    }
    int x,y;
    for(int i=1;i<n;i++)
    {
        x=read(); y=read();
        add(x,y); add(y,x);
    }
    getans();
    printf("%d\n",ans);
    return 0;
}
01-20 05:24