记录编号	585740	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2007]树网的核(加强版)	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	1.871 s
提交时间	2023-12-21 22:13:57	内存使用	53.48 MiB

#include <bits/stdc++.h> 
using namespace std;
#define ll long long
const int N = 1e6+10,mod = 10007;
int n,m;
struct made{
    int nx,ver,ed;
}e[N<<1];
int hd[N],tot,f[N],son[N],st,en;
ll d[N],s,ans = INT_MAX;
bool v[N];
void add(int x,int y,int z){
    tot++;
    e[tot].ver = y,e[tot].nx = hd[x],e[tot].ed = z,hd[x] = tot;
}
void dfs1(int x,int fa,int &u){
    f[x] = fa;
    for(int i = hd[x];i;i = e[i].nx){
        int y = e[i].ver,z = e[i].ed;
        if(y == fa)continue;
        d[y] = d[x] + z;
        if(d[y] > s)s = d[y],u = y;
        dfs1(y,x,u);
    }
}
ll de[N];
void dfs2(int x,int fa){
    for(int i = hd[x];i;i = e[i].nx){
        int y = e[i].ver,z = e[i].ed;
        if(y == fa || v[y])continue;
        de[y] = de[x] + z;
        s = max(s,de[y]);
        dfs2(y,x);
    }
}
void find(){
    memset(d,0,sizeof(d));
    dfs1(1,0,st);
    memset(d,0,sizeof(d));s = 0;
    memset(f,0,sizeof(f));
    dfs1(st,0,en);
}//dfs求直径
bool check(ll x){
    int p = en,q = st;
    while(d[en] - d[f[p]] <= x && f[p])p = f[p];
    while(d[son[q]] - d[st] <= x && son[q])q = son[q];
    if(d[p] - d[q] > m)return 0;
    for(int i = q;i;i = f[i])
        if(i == p)return 1;
    memset(v,0,sizeof(v));
    memset(de,0,sizeof(de));
    for(int i = p;1;i = f[i]){
        v[i] = 1;
        if(i == q)break;
    }
    s = 0;
    for(int i = p;1;i = f[i]){
        dfs2(i,0);
        if(i == q)break;
    }
    return (s <= x);
}
int main(){
    freopen("core_hard.in","r",stdin);
    freopen("core_hard.out","w",stdout);
    scanf("%d%d",&n,&m);
    tot = 1;
    for(int i = 1;i < n;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z),add(y,x,z);
    }
    find();
    for(int i = en;i;i = f[i])son[f[i]] = i;
    ll l = 0,r = 1e18;
    while(l < r){
        ll mid = l + r >> 1;
        if(check(mid))r = mid;
        else l = mid + 1;
    }
    printf("%lld\n",l);
    
    return 0;
    
}