题解：P15472 [ICPC 2024 WF] Steppe on It 草原上的加速

· · 题解

四处寻找可以写题解的题目中

然后碰瓷紫题成功。

::::info[懒得看语文题目的过来形式化题意]{open}

给定一个无向无环图，也就是一棵树 V。

需要选择一个村庄集合为：

S\subseteq V,\qquad |S|=f,

在其中放置消防车。对任意村庄 v，其响应时间为到最近消防车所在村庄的距离：

r_S(v)=\min_{s\in S} d(v,s).

整个方案的保证响应时间为：

R(S)=\max_{v\in V} r_S(v) =\max_{v\in V}\min_{s\in S} d(v,s).

目标是求最小可能保证响应时间：

R^*=\min_{S\subseteq V,\, |S|=f} R(S).

等价地，求最小的非负整数 R，使得存在 f 个村庄作为中心，满足每个村庄到某个中心的距离都不超过 R，即：

\exists S\subseteq V,\ |S|=f,\quad \forall v\in V,\quad \min_{s\in S} d(v,s)\le R.

也就是在树的节点上选 f 个中心，使所有节点到最近中心的最大距离最小。

输入中第 i 行 (v_i,t_i) 表示树边 (i,v_i)，权为 t_i，其中 v_i<i。输出上述最小值 ans。

形式化题意比正经讲做法难多了 QwQ。

::::

做法

其实可以直接二分答案判断：是否存在不超过 f 个消防站，使得每个点到最近消防站的距离都不超过 c。

怎么判断呢，其实可以从叶子向上贪心地放消防站，具体贪心方式配合 chk 函数代码食用吧。

bool chk(ll c,ll&n,ll&m,vector<ll>&w,vector<ll>&fa)//定义如题目
{
    ll cnt=0;//要放多少站点
    vector<ll> f(n+1);//i 的子树中，尚未被覆盖的点到 i 的最大距离。
    //其中 f[i]=0 代表 i 还没被覆盖
    //f[i]=-1 代表子树内部覆盖完毕
    vector<ll> g(n+1,INF);
    //消防站到 i 的最小距离
    //初始化 INF 就是没有的意思
    for(ll i=n;i>1;--i)//题目保证了父亲编号严格小于子节点
    {
        if(f[i]!=-1 && g[i]!=INF && g[i]+f[i]<=c) f[i]=-1;//假如我们可以用子树里面的消防站覆盖到 i 的话
        ll t=fa[i];
        if(f[i]!=-1 && f[i]+w[i]>c)//假如我们必须在 i 放消防站
        {
            ++cnt;//增加（我是不是太详细了？）
            if(cnt>m) return 0;//大于最大值，直接返回
            g[i]=0;
            f[i]=-1;
            //距离肯定是 0，顺便标记一下
        }
        g[t]=min(g[t],g[i]+w[i]);//父亲离消防站的距离的更新
        if(f[i]!=-1)f[t]=max(f[t],w[i]+f[i]);//父亲的可达性
    }
    if(f[1]!=-1)
    {
        if(g[1]!=INF && f[1]+g[1]<=c)f[1]=1;
        else cnt++;
    }
    return cnt<=m;//尾判
}

判断就这样，所有该说的都说了，主函数比我的 A+B 还简单。

ll n,m;
cin >> n >> m;
vector<ll> fa(n+1);
vector<ll> w(n+1);
for(ll i=2; i<=n; ++i) cin >> fa[i] >> w[i];

ll l=0;
ll r=inf;//开 1e9 够用
ll ans=-1;
while(l<=r)//快乐的二分
{
    ll mid=(l+r)>>1;
    if(chk(mid,n,m,w,fa))
    {
        r=mid-1;
        ans=mid;
    }
    else l=mid+1;
}
cout << ans;
僕を連れてって 浸み込んでしまう前に
見えないままやられちゃうとか どうにも出来ないからさ
離せない手はずっと濡れていて いつか落としてしまうこと
まだ気付いてなかった