CF1004E Sonya and Ice Cream 题解

Zskioaert1106 · 2026-07-24 13:21:29 · 题解

题目传送门：CF1004E Sonya and Ice Cream

就算纯直径做法比较难想，但二分做法是真没有紫。

题意重述

给定一棵树，选择一条长度不超过 k 的链，使所有点到链的最大距离最小。

其中长度指点的数量，两点之间的距离指两点简单路径上边权之和，点到链的距离为点到链上任意一点距离的最小值。

题目分析

看到最小化，想到二分答案。设这个距离为 lim，我们记 a_i 为根到 i 的路径长度，mx_i 为 i 子树里最大的 a_j，那么：

• 不妨令满足 mx_u-a_u \leqslant lim < mx_u-a_{fa_u} 的 u 做链头。

证明：将链延伸到 u 的上面显然没用，但不到 u，哪怕在 fa_u，也存在到不了的点。

因此不妨以 u 为根再搜一次，找出来此时所有满足上述条件的点 v。

合法情况：

• 不存在 u。

• 不存在 v。

做完了。代码也非常简单。

这个问题转化成了类似判定性的两次 DFS 求树的直径。

代码实现

#include<bits/stdc++.h>
using namespace std;
constexpr int N=100005;
int n,k,fa[N],dep[N],a[N],mx[N];
struct edge{
    int v,w;
};
vector<edge>e[N];
void dfs(int x){
    dep[x]=dep[fa[x]]+1;
    for(edge i:e[x]){
        int u=i.v;
        if(u==fa[x])continue;
        fa[u]=x;
        mx[u]=a[u]=a[x]+i.w;
        dfs(u);
        mx[x]=max(mx[x],mx[u]);
    }
}
int main(){
    cin>>n>>k;
    for(int i=n,u,v,w;--i;){
        cin>>u>>v>>w;
        e[u].push_back({v,w}),e[v].push_back({u,w});
    }
    dfs(1);
    int ans;
    for(int l=0,r=mx[1],lim;l<=r;){
        lim=(l+r)/2;
        int x=0,y=0,cnt=0;
        for(int i=1;i<=n;i++)
            if(mx[i]-a[i]<=lim&&lim<mx[i]-a[fa[i]])x=i;
        if(!x)ans=lim,r=lim-1;
        else{
            fa[x]=a[x]=mx[x]=0;
            dfs(x);
            for(int i=1;i<=n;i++)
                if(mx[i]-a[i]<=lim&&lim<mx[i]-a[fa[i]])y=i,cnt++;
            if(!cnt||cnt==1&&dep[y]<=k)ans=lim,r=lim-1;
            else l=lim+1;
        }
    }
    cout<<ans;
    return 0;
}

AC on CF。