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
| #include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=3e5+10;
const int NM=1e6+10;
const double eps=1e-8;
#define ll long long
const int inf=1e9+7;
using namespace std;
struct edge{int t,v;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y,int vul){o->t=y;o->v=vul;o->next=h[x];h[x]=o++;}
ll read(){
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
int n,K;
bool vis[MAXN];
ll dis[MAXN];
int cnt[MAXN];
int base,key,rt;
int sz[MAXN],maxx[MAXN];
void get_root(int x,int pre){
sz[x]=1;maxx[x]=0;
link(x){
if(j->t==pre||vis[j->t])continue;
get_root(j->t,x);
sz[x]+=sz[j->t];maxx[x]=max(maxx[x],sz[j->t]);
}
maxx[x]=max(maxx[x],base-sz[x]);
if(key>maxx[x])key=maxx[x],rt=x;
}
int st[MAXN],tot,ans,St[MAXN],tot1;
int num[NM],Num[NM];
void dfs(int x,int pre){
if(dis[x]<=K)st[++tot]=dis[x],num[dis[x]]=min(num[dis[x]],cnt[x]),St[++tot1]=dis[x];
link(x){
if(j->t==pre||vis[j->t])continue;
dis[j->t]=dis[x]+j->v;cnt[j->t]=cnt[x]+1;
dfs(j->t,x);
}
}
void solve(int x){
vis[x]=1;tot1=0;Num[0]=0;
link(x){
if(vis[j->t])continue;
tot=0;dis[j->t]=j->v;cnt[j->t]=1;dfs(j->t,x);
inc(i,1,tot)ans=min(ans,num[st[i]]+Num[K-st[i]]);
inc(i,1,tot)Num[st[i]]=min(Num[st[i]],num[st[i]]),num[st[i]]=inf;
}
inc(i,1,tot1)Num[St[i]]=inf;
Num[0]=inf;
link(x){
if(vis[j->t])continue;
key=inf;base=sz[j->t];get_root(j->t,0);
solve(rt);
}
}
int main(){
n=read();K=read();
int x,y,z;
inc(i,1,K)num[i]=Num[i]=inf;
inc(i,2,n)x=read()+1,y=read()+1,z=read(),add(x,y,z),add(y,x,z);
ans=inf;key=inf;base=n;get_root(1,0);
solve(rt);
if(ans==inf)printf("-1\n");
else printf("%d\n",ans);
}
|