#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
const int maxn=2e5+5;
const int maxk=1e6+5;
vector<pii> adj[maxn];
pii path[maxk];
int vis[maxn],siz[maxn];
int n,k,a,b,c;
int ans;
queue<pii> q;
int dfssiz(int x,int p){
int sizz=1;
for(pii i:adj[x]){
if(i.f==p||vis[i.f]) continue;
sizz+=dfssiz(i.f,x);
}
siz[x]=sizz;
return sizz;
}
int dfsget(int x,int p,int c){
for(pii i:adj[x]){
if(i.f==p||vis[i.f]) continue;
if(siz[i.f]>=siz[c]>>1) return dfsget(i.f,x,c);
}
return x;
}
void dfssolve(int x,int p,int d,int dd,int c){
if(dd>k) return;
if(dd==k){
ans=min(ans,d);
return;
}
if(path[k-dd].s==c) ans=min(ans,path[k-dd].f+d);
for(pii i:adj[x]){
if(i.f==p||vis[i.f]) continue;
dfssolve(i.f,x,d+1,dd+i.s,c);
}
q.push({d,dd});
}
int getcentroid(int x){
dfssiz(x,-1);
return dfsget(x,-1,x);
}
void solve(int x){
if(vis[x]) return;
int c=getcentroid(x);
path[0]={0,c};
pii cur;
for(pii i:adj[c]){
if(vis[i.f]) continue;
dfssolve(i.f,c,1,i.s,c);
while(!q.empty()){
cur=q.front();
q.pop();
if(path[cur.s].s!=c) path[cur.s]={cur.f,c};
else path[cur.s].f=min(cur.f,path[cur.s].f);
}
}
vis[c]=1;
for(pii i:adj[c]){
if(vis[i.f]) continue;
solve(i.f);
}
}
signed best_path(signed N,signed K,signed H[][2],signed L[]){
n=N;k=K;
ans=LLONG_MAX;
memset(path,0xff,sizeof(path));
for(int i=0;i<n-1;i++){
adj[H[i][0]].pb({H[i][1],L[i]});
adj[H[i][1]].pb({H[i][0],L[i]});
}
solve(0);
if(ans==LLONG_MAX) return -1;
return ans;
}
