题解 P3523 【[POI2011]DYN-Dynamite】

题解- P3523 DYN-Dynamite

题目意思

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

双倍经验

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

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

首先我们设几个变量：

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

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

$mid$ 表示我们二分出来的答案

对于求 $f_i,g_i$ 还是比较基础的：

$f_u=\min\{f_v+1,f_u\},v∈u$

$g_u=\max\{g_v+1,g_u\},v∈u$

但是重点来了！

要分 $3$ 种情况来讨论：

$(i) f_u\leq mid$ 并且 $u$ 为关键点 $g_u=\max\{g_u,0\}$

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

$(ii) f_u+g_u\leq mid$

现在 $g_u=-oo$ ,因为以 $u$ 为子树的所有点都可以被覆盖，所以没有无法覆盖的点故 $g_u=-oo$

$(iii) g_u=mid$

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

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

#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;
}