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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5+10;
int head[N],tot;
int maxp[N],siz[N],tmp[N*10],cnt,d[N];
int sum,rt;
bool vis[N];
int judge[N*10];
int dis[N];
int n,k,ans=INT_MAX;
struct edge{
int v,w,nex;
edge(){}
edge(int v, int w, int nex) : v(v), w(w), nex(nex) {}
}edges[N<<1];
void add(int u,int v,int w){
edges[tot]=edge(v,w,head[u]);
head[u]=tot++;
}
void getrt(int u,int fa){
maxp[u]=0,siz[u]=1;
for(int i=head[u];~i;i=edges[i].nex){
int v=edges[i].v;
if(vis[v]||v==fa)continue;
getrt(v,u);
siz[u]+=siz[v];
if(maxp[u]<siz[v])maxp[u]=siz[v];
}
maxp[u]=max(maxp[u],sum-siz[u]);
if(maxp[u]<maxp[rt])rt=u;
}
void getdis(int u,int fa,int deep){
if(dis[u]>k)return ;
tmp[cnt]=dis[u];
d[cnt++]=deep;
for(int i=head[u];~i;i=edges[i].nex){
int v = edges[i].v;
if(v==fa||vis[v])continue;
dis[v]=dis[u]+edges[i].w;
getdis(v,u,deep+1);
}
}
void solve(int u){
judge[0]=0;
queue<int>que;
for(int i=head[u];~i;i=edges[i].nex){
int v = edges[i].v;
if(vis[v])continue;
cnt = 0;
dis[v]=edges[i].w;
getdis(v,u,1);
for(int j=0;j<cnt;j++)ans=min(ans,judge[k-tmp[j]]+d[j]);
for(int j=0;j<cnt;j++)judge[tmp[j]]=min(judge[tmp[j]],d[j]),que.push(tmp[j]);
}
while(!que.empty()){
judge[que.front()]=1e9+10;
que.pop();
}
}
void divide(int u){
vis[u]=1;
solve(u);
for(int i=head[u];~i;i=edges[i].nex){
int v = edges[i].v;
if(vis[v])continue;
maxp[rt=0]=sum=siz[v];
getrt(v,0);
getrt(rt,0);
divide(rt);
}
}
int main(){
memset(head,-1,sizeof(head));
scanf("%d %d",&n,&k);
for(int i=1;i<n;i++){
int u,v,w;
scanf("%d %d %d",&u,&v,&w);
u++;v++;
add(u,v,w);
add(v,u,w);
}
maxp[0]=sum=n;
memset(judge,0x3f,sizeof(judge));
getrt(1,0);
getrt(rt,0);
divide(rt);
printf("%d\n",ans>=n?-1:ans);
}
|