#include "race.h"
#include "bits/stdc++.h"
using namespace std;
const int N = 200001;
const int INF = 1e9;
int n;
vector < pair < int , int > > G[N];
vector < pair < int , pair<int,int> > > dis[N];
void add_edge(int u,int v,int w){
G[u].push_back({v , w});
G[v].push_back({u , w});
}
int sub[N] , par[N] , timer = 0;
bool is_rmv[N];
int tin[N] , tout[N];
void DFS(int v , int p)
{
par[v] = p;
tin[v] = ++timer;
for(pair < int , int > nxt : G[v])
{
int u = nxt.first;
if(u == p) continue;
DFS(u , v);
}
tout[v] = timer;
}
bool is_anc(int u , int v)
{
return (tin[v] >= tin[u] && tout[u] >= tout[v]);
}
int gsz(int v , int p){
sub[v] = 1;
for(pair < int , int > nxt : G[v]){
int u = nxt.first;
if(u == p or is_rmv[u]) continue;
sub[v] += gsz(u , v);
}
return sub[v];
}
int find_centro(int v , int p , int need){
for(pair < int , int > nxt : G[v])
{
int u = nxt.first;
if(u == p or is_rmv[u] or sub[u] <= need / 2) continue;
return find_centro(u , v , need);
}
return v;
}
map < pair < int , pair < int , int > > , int > mp;
map < pair < int , pair < int , int > > , int > can;
void dfs(int v , int p , int imp , int nd , int wd , int centro)
{
dis[v].push_back({centro , {nd,wd}});
if(!can[{centro , {imp , wd}}])
{
can[{centro , {imp , wd}}] = 1;
mp[{centro , {imp , wd}}] = INF;
}
mp[{centro , {imp , wd}}] = min(mp[{centro , {imp , wd}}] , nd);
for(pair < int , int > nxt : G[v])
{
int u = nxt.first;
if(u != p && !is_rmv[u]) dfs(u , v , imp , nd + 1 , wd + nxt.second , centro);
}
}
void DFS(int centro)
{
dis[centro].push_back({centro , {0,0}});
for(pair < int , int > nxt : G[centro])
{
int u = nxt.first;
int w = nxt.second;
if(!is_rmv[u]) dfs(u , centro , u , 1 , w , centro);
}
}
void build(int v)
{
int comp_sz = gsz(v , -1);
int centro = find_centro(v , -1 , comp_sz);
DFS(centro);
is_rmv[centro] = 1;
for(pair < int , int > nxt : G[centro]){
int u = nxt.first;
if(!is_rmv[u]) build(u);
}
}
int get(int v , int k)
{
int ans = INF;
for(pair < int , pair<int,int> > nxt : dis[v])
{
int centro = nxt.first;
int dist = nxt.second.first;
int wdist = nxt.second.second;
int node = -1;
int need = k - wdist;
for(pair < int , int > U : G[centro])
{
if(U.first == par[centro]) continue;
int u = U.first;
if(is_anc(u , v)) node = u;
}
if(node == -1) node = par[centro];
for(pair < int , int > U : G[centro])
{
if(U.first == node) continue;
if(can[{centro , {U.first , need}}]) ans = min(ans , dist + mp[{centro , {U.first , need}}]);
}
}
return ans;
}
int best_path(int N , int K , int H[][2] , int L[])
{
n = N;
for(int i = 0;i < N - 1;i++) add_edge(H[i][0] , H[i][1] , L[i]);
build(0);
DFS(0 , -1);
int ans = INF;
for(int i = 0;i < N;i++) ans = min(ans , get(i , K));
if(ans == INF) ans = -1;
return ans;
}
