Codeforces

Luogu

分析

显然选的路径是直径的一部分。为了方便，把直径上的点重编号为 $1\sim cnt$。

我们把这棵树想象成一条链上挂了一些子树。那么设一个 $maxdis_i$ 表示 $i$ 子树中到 $i$ 最远的点的距离。

一个暴力做法是枚举选的路径 $[l,r]$，此时最大距离就是 $1\sim l$ 的距离、$r\sim cnt$ 的距离、$\max_{i=l}^r\left\{maxdis_i\right\}$ 三者的最大值。这样子大概是 $O(n^3)$ 的。

考虑到我们选的路径一定越长越好，因此只需要枚举左端点 $l$，右端点即为 $l+k-1$。这样子就变成 $O(n^2)$ 了。

剩下的就很简单了。我们用 ST 表求 $maxdis$ 的最大值，这样就是 $O(n\log n)$ 的了。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,k;

struct edge { int v,w,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v,int w) {
    static int cnt=0;
    e[++cnt]=(edge){v,w,head[u]},head[u]=cnt;
}

int rt1,rt2;
int dis[N],fa[N];
inline void dfs1(int u,int f) {
    if (dis[u]>dis[rt1]) rt1=u;
    for (re int i=head[u];i;i=e[i].nxt)
        if (e[i].v!=f) dis[e[i].v]=dis[u]+e[i].w,dfs1(e[i].v,u);
}
inline void dfs2(int u,int f) {
    fa[u]=f;
    if (dis[u]>dis[rt2]) rt2=u;
    for (re int i=head[u];i;i=e[i].nxt)
        if (e[i].v!=f) dis[e[i].v]=dis[u]+e[i].w,dfs2(e[i].v,u);
}

int cnt=0,lend=0;
int in[N],maxdis[N],w[N];
int lg[N],st[17][N],sum[N];
inline void dfs3(int u,int f) {
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==f) continue;
        w[v]=e[i].w,dfs3(v,u);
        if (!in[v]) maxdis[u]=max(maxdis[u],maxdis[v]+e[i].w);
    }
}
inline void init_diameter() {
    for (re int i=rt2;i;i=fa[i]) in[i]=1,++cnt;
    dfs3(rt1,0);
    for (re int i=2;i<=n;++i) lg[i]=lg[i>>1]+1;
    for (re int i=rt2,j=1;i;i=fa[i],++j) st[0][j]=maxdis[i];
    for (re int i=1;i<17;++i)
        for (re int j=1;j+(1<<i)-1<=cnt;++j)
            st[i][j]=max(st[i-1][j],st[i-1][j+(1<<(i-1))]);
    for (re int i=rt2,j=1;i;i=fa[i],++j) sum[j]=w[i],lend+=w[i];
    for (re int i=1;i<=cnt;++i) sum[i]+=sum[i-1];
}
inline int query(int l,int r) {
    int t=lg[r-l+1];
    return max(st[t][l],st[t][r-(1<<t)+1]);
}

int main() {
    n=read(),k=read();
    if (n==1) { puts("0"); return 0; }
    for (re int i=1;i<n;++i) {
        int u=read(),v=read(),w=read();
        addEdge(u,v,w),addEdge(v,u,w);
    }
    dfs1(1,0),dfs2(rt1,0);
    init_diameter();
    if (k>cnt) printf("%d\n",query(1,cnt));
    else {
        int ans=2e9;
        for (re int i=1;i+k-1<=cnt;++i) {
            int tmp=max(sum[i-1],lend-sum[i+k-2]);
            ans=min(ans,max(tmp,query(i,i+k-1)));
        }
        printf("%d\n",ans);
    }
    return 0;
}