1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
| #include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int n, k, hea[100005], cnt, uu, vv, ww, dis[100005], fa[100005], len[100005], mxlen, d[100005];
bool vis[100005];
vector<int> zj, jl;
struct Edge{
int too, nxt, val;
}edge[200005];
void add_edge(int fro, int too, int val){
edge[++cnt].nxt = hea[fro];
edge[cnt].too = too;
edge[cnt].val = val;
hea[fro] = cnt;
}
void dfs(int x, int f){
fa[x] = f;
mxlen = max(mxlen, dis[x]);
for(int i=hea[x]; i; i=edge[i].nxt){
int t=edge[i].too;
if(t!=f && !vis[t]){
dis[t] = dis[x] + edge[i].val;
dfs(t, x);
}
}
}
int main(){
cin>>n>>k;
for(int i=1; i<n; i++){
scanf("%d %d %d", &uu, &vv, &ww);
add_edge(uu, vv, ww);
add_edge(vv, uu, ww);
}
dfs(1, 0);
int st=1;
for(int i=1; i<=n; i++)
if(dis[i]>dis[st])
st = i;
dis[st] = 0;
dfs(st, 0);
st = 1;
for(int i=1; i<=n; i++)
if(dis[i]>dis[st])
st = i;
for(; st; st=fa[st])
zj.push_back(st);
reverse(zj.begin(), zj.end());
for(int i=0; i<zj.size(); i++){
jl.push_back(dis[zj[i]]);
vis[zj[i]] = true;
}
for(int i=0; i<zj.size(); i++){
int x=zj[i];
dis[x] = mxlen = 0;
dfs(x, 0);
len[i] = mxlen;
}
k = min(k, (int)zj.size());
mxlen = 0x3f3f3f3f;
int ll=1, rr=0, j=0;
for(int i=0; i<=zj.size()-k; i++){
while(j<=i+k-1){
while(ll<=rr && len[d[rr]]<=len[j]) rr--;
d[++rr] = j;
j++;
}
while(d[ll]<i) ll++;
mxlen = min(mxlen, max(max(len[d[ll]], jl[i]), jl[zj.size()-1]-jl[i+k-1]));
}
cout<<mxlen<<endl;
return 0;
}
|