题解：CF1004E Sonya and Ice Cream

· · 题解

捕捉到关键词“最大距离”，想到树的直径。

首先，树的直径有一个非常重要的性质：到每个点距离最远的点必定是树的两个端点之一。

放在这道题，就是使路径上的点到直径两端的距离最小，也就是说，使直径两端到路径的距离尽可能小，不难想到直接把路径放在直径上。

现在我们重新画个图 （图丑勿喷）：

其中红色的线段是路径，蓝色线段是路径到直径两端经过的部分，黄色是每个点上挂下来的子树内的最长路径，最终的答案就是在所有黄色和蓝色的距离中取 \max。

这时候可能就有人问啊，蓝色线段上挂下来的子树（虚线部分）里的答案不用算吗？显然不用，因为如果它能够影响到最终 \max 的答案的话，一定比蓝色线段长，就成了新的直径了，而这显然是不可能的。

然后我们又注意到 （其实这个应该是看完题第一眼注意到的东西吧 QwQ），路径变长答案肯定不会增加，那么我们就把路径长度固定为 k，滑动窗口计算黄色最大距离，顺便在循环的时候算一下蓝色部分，这题就做完了，时空复杂度均为 O(n)。

::::success[code（码风飘逸，重点看思路即可）]

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+3;
#define int long long
int n,k,dis[N],dis2[N],dep[N],r1,r2,fa[N];
int vis[N],lg[N],l=0,r=-1,q[N],ans=1e18;
struct node{
    int x,w;
};
vector<node>v[N];
vector<int>g;
int dfs(int x,int f){
    int res=dis[x];//黄色路径最大值
    for(auto y:v[x]){
        if(y.x==f||vis[y.x]) continue;
        dis[y.x]=dis[x]+y.w;//到根距离
        dep[y.x]=dep[x]+1;
        fa[y.x]=x;
        res=max(res,dfs(y.x,x));
    }
    return res;
}
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;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    n=read();k=read();
    for(int i=1;i<n;i++){
        int x,y,z;x=read();y=read();z=read();
        v[x].push_back({y,z});v[y].push_back({x,z});
    }
  //以上为读入
    dfs(1,0);
    int mx=-1;
    for(int i=1;i<=n;i++) if(dis[i]>mx) r1=i,mx=dis[i];
    dis[r1]=dep[r1]=fa[r1]=0;mx=-1;
    dfs(r1,0);
    for(int i=1;i<=n;i++) if(dis[i]>mx) r2=i,mx=dis[i];
    //以上为计算直径的两个端点 r1,r2
    for(int i=r2;i;i=fa[i]) g.push_back(i),vis[i]=1;
    //以上为把路径提取出来
    for(int i=0;i<g.size();i++){
        int x=g[i];
        int t=dis[x];
        dis[x]=0;
        lg[i]=dfs(x,0);
        dis[x]=t;
    }
    //以上为计算每个点对应的黄色线段最大距离 lg
    int sum=dis[r2];
    for(int i=0;i<g.size();i++){
        while(l<=r&&lg[q[r]]<lg[i]) r--;
        q[++r]=i;
        while(l<=r&&q[l]<=i-k+1) l++;
        //以上为滑动窗口求最大值
        ans=min(ans,max({lg[q[l]],dis[g[i]],(i<k-1?0:sum-dis[g[i-k+1]])}));
        //黄色线段最大值；到 r1 的距离；到 r2 的距离（注意直径可能比 k 短）
    }
    cout<<ans;
    return 0;
}

::::

AC 记录