#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<ll,ll>;
const ll MXN = 2e5;
const ll MXK = 1e6;
vector<ii> AL[MXN];
bool removed[MXN];
ll N, K;
ll subtreeSize[MXN];
// get size of a subtree
ll getSize(ll v, ll p)
{
ll res = 1;
for(auto& [u,w]: AL[v])
{
if(u==p) continue;
if(removed[u]) continue;
res += getSize(u,v);
}
subtreeSize[v] = res;
return res;
}
// find the centroid
// of a connected component
ll findCentroid(ll v, ll p, ll n)
{
bool found = true;
ll sum = 1;
for(auto& [u,w]: AL[v])
{
if(u==p) continue;
if(removed[u]) continue;
sum += subtreeSize[u];
if(subtreeSize[u]>(n/2))
{
found = false;
break;
}
}
if((n-sum)>(n/2)) found = false;
if(found) return v;
for(auto& [u,w]: AL[v])
{
if(u==p) continue;
if(removed[u]) continue;
ll r = findCentroid(u,v,n);
if(r!=-1) return r;
}
return -1;
}
// saves the depth at which was found
// the minimum depth and the second minimum
ll found[MXK+1];
void gather(ll v, ll p, ll d, ll s)
{
if(s>K) return;
if(found[s]==-1) found[s] = d;
else found[s] = min(found[s],d);
for(auto& [u,w]: AL[v])
{
if(u==p) continue;
if(removed[u]) continue;
gather(u,v,d+1,s+w);
}
}
ll check(ll v, ll p, ll d, ll s)
{
if(s>K) return -1;
ll o = K-s;
ll res = -1;
if(found[o]!=-1) res = found[o]+d;
for(auto& [u,w]: AL[v])
{
if(u==p) continue;
if(removed[u]) continue;
ll r = check(u,v,d+1,s+w);
if(r!=-1)
{
if(res!=-1) res = min(res,r);
else res = r;
}
}
return res;
}
void clear(ll v, ll p, ll s)
{
if(s>K) return;
found[s] = -1;
for(auto& [u,w]: AL[v])
{
if(u==p) continue;
if(removed[u]) continue;
clear(u,v,s+w);
}
}
// returns -1 or minimum highways
// such that v is included in the path
ll process(ll v)
{
vector<ll> vec;
ll res = -1;
for(auto& [u,w]: AL[v])
{
if(removed[u]) continue;
found[0]=0;
ll r = check(u,v,1,w);
if(r!=-1)
{
if(res!=-1) res = min(res,r);
else res = r;
}
gather(u,v,1,w);
}
for(auto& [u,w]: AL[v]) clear(u,v,w);
return res;
}
// returns -1 or minimum highways
// in the whole connected component
// divide and conquer
ll DACE(ll v)
{
ll sz = getSize(v,v);
ll c = findCentroid(v,v,sz);
ll res = process(c);
removed[c] = 1;
for(auto& [u,w]: AL[c])
{
if(removed[u]) continue;
ll res_u = DACE(u);
if(res_u!=-1){
if(res==-1) res=res_u;
else res=min(res, res_u);
}
}
return res;
}
int best_path(int n, int k, int H[][2], int L[])
{
N = n,K = k;
for(ll i=1;i<=K;i++) found[i]=-1;
for(ll i=0;i<N-1;i++)
{
ll a=H[i][0],b=H[i][1],w=L[i];
AL[a].emplace_back(b,w);
AL[b].emplace_back(a,w);
}
return DACE(0);
}
