bzoj-2525 Dynamite

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(g[1]+f[1]>limit)
则1这个点也要放引爆
对于其它点
if(f[i]+g[i]<=mid) g[i]=INF
if(g[i]==mid) 必须引爆x

/*

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; //以i为根的子树中已经引爆的点离i最近的距离

    if(a[x])

	    g[x]=0; //这以i为根的子树中未引爆的点离i最远的距离

    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);//找一个离x最近的引爆点

        g[x]=max(g[x],g[b[i].to]+1);//一个离x最远的未引爆点

    }

    if(g[x]+f[x]<=limit)

	//以x为根的子树，存在一个引爆点可以在规定时间内引爆那些未引爆点

	   g[x]=-INF;

    if(g[x]==limit)

	//离x最远的一个未能被引爆的点离x的距离=limit,说明x点必须被点燃

	{

        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;

}

巴特西

bzoj-2525 Dynamite

最新文章

热门文章