题解 P3523 【[POI2011]DYN-Dynamite】

题解- P3523 DYN-Dynamite

• 题目意思

  就是在一颗树中选个点使得这个点到关键点的距离最大值最小。

• 

  双倍经验

  总算看懂题解来重新理解一遍，加深记忆。。

  回归正题，因为题目要我们求最大值最小显然会想到二分。

  首先我们设几个变量：

  表示以为子树最近选择节点的距离

  表示以为子树最远还没有选择的关键点距离

  表示我们二分出来的答案

  对于求还是比较基础的：

  

  

  但是重点来了！

  要分种情况来讨论：

  并且为关键点

  如何理解呢？因为最近的点暂时无法满足条件

  

  现在,因为以为子树的所有点都可以被覆盖，所以没有无法覆盖的点故

  

  现在这个点已经最远，无法选择更远的啦。所以这个点必须要选，故因为自己选自己最近为，。

  但是最后还要判断根节点的情况就可以了。

#include <bits/stdc++.h>
using namespace std;

inline int read()
{
    int sum=0,ff=1; char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-') ff=-1;
        ch=getchar();
    }
    while(isdigit(ch))
        sum=sum*10+(ch^48),ch=getchar();
    return sum*ff;
}

const int N=5e5+5;

int n,m,cnt,f[N],g[N],is[N],head[N],ans,gs;

struct nood
{
    int nex,to;
};
nood e[N*2];

inline void jia(int u,int v)
{
    e[++cnt].nex=head[u];
    head[u]=cnt;
    e[cnt].to=v;
}

inline void dfs(int u,int fa,int x)
{
    f[u]=1e9;
    g[u]=-1e9;
    for ( int i=head[u];i;i=e[i].nex )
    {
        int v=e[i].to;
        if(v==fa) continue;
        dfs(v,u,x);
        f[u]=min(f[v]+1,f[u]);
        g[u]=max(g[v]+1,g[u]);
    }
    if(is[u]&&f[u]>x) g[u]=max(g[u],0);
    if(g[u]+f[u]<=x) g[u]=-1e9;
    if(g[u]==x)
        gs++,g[u]=-1e9,f[u]=0;
}

inline bool check(int mid)
{
    gs=0;
    dfs(1,0,mid);
    gs+=(g[1]>=0);
    return gs<=m;
}

int main()
{
    n=read();
    m=read();
    for ( int i=1;i<=n;i++ ) 
        is[i]=read();
    for ( int i=1;i<n;i++ )
    {
        int x,y;
        x=read(),y=read();
        jia(x,y);
        jia(y,x);
    }
    int l=0,r=n;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(check(mid))
        {
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    printf("%d\n",ans);
    return 0;
}