#include <bits/stdc++.h>
//#include "race.h"
using namespace std;
using ll = long long;
const int NMAX = 2e5;
const int INF = 1e9;
const int MAXLOG = 18;
int parent[NMAX+1];
bool is_removed[NMAX+1];
int sz[NMAX+1];
vector <pair<ll, int>> distSubtree[NMAX+1];
vector <pair<int, int>> edges[NMAX+1];
vector<int> centroidEdges[NMAX+1];
int calcSize( int node, int parent ) {
sz[node] = 1;
for( auto vec: edges[node] ) {
if( vec.first != parent && !is_removed[vec.first] )
sz[node] += calcSize( vec.first, node );
}
return sz[node];
}
int find_centroid( int node, int parent, int totalSz ) {
for( auto vec: edges[node] ) {
if( vec.first != parent && !is_removed[vec.first] && sz[vec.first] > totalSz / 2 )
return find_centroid( vec.first, node, totalSz );
}
return node;
}
struct Ancestor{
ll sum;
int length;
};
Ancestor anc[NMAX+1][MAXLOG+3];
int depth[NMAX+1];
void updDist( int init, int node, int parent, int dep, ll sumEdges ) {
distSubtree[init].push_back( { sumEdges, node } );
anc[node][depth[init]] = { sumEdges, dep };
for( auto vec: edges[node] ) {
if( !is_removed[vec.first] && vec.first != parent )
updDist( init, vec.first, node, dep + 1, sumEdges + vec.second );
}
}
void decomposition( int node, int centroidParent, int dep ) {
int totalSz = calcSize( node, -1 );
int centroid = find_centroid( node, -1, totalSz );
depth[centroid] = dep;
is_removed[centroid] = true;
parent[centroid] = centroidParent;
centroidEdges[centroid].push_back( centroidParent );
centroidEdges[centroidParent].push_back( centroid );
updDist( centroid, centroid, -1, 0, 0 );
for( auto vec: edges[centroid] ) {
//cout << vec.first << " ";
if( !is_removed[vec.first] )
decomposition( vec.first, centroid, dep + 1 );
}
}
map<ll, int> dp;
int ans = INF;
void dfs( int node, int i, int type, int k ) {
ll sum = anc[node][depth[i]].sum;
int length = anc[node][depth[i]].length;
if( type == 0 && dp.find( k - sum ) != dp.end() )
ans = min( ans, dp[k-sum] + length );
else if( type == 1 ) {
if( dp[sum] )
dp[sum] = min( dp[sum], length );
else
dp[sum] = length;
}
for( auto vec: centroidEdges[node] ) {
if( vec != parent[node] )
dfs( vec, i, type, k );
}
}
int best_path( int n, int k, int h[][2], int len[] ) {
int i;
for( i = 0; i < n - 1; i++ ) {
edges[h[i][0]].push_back( { h[i][1], len[i] } );
edges[h[i][1]].push_back( { h[i][0], len[i] } );
}
decomposition( 0, -1, 0 );
ans = INF;
for( i = 0; i < n; i++ ) {
dp.clear();
dp[0] = 0;
for( auto vec: centroidEdges[i] ) {
if( vec != parent[i] ) {
dfs( vec, i, 0, k );
dfs( vec, i, 1, k );
}
}
}
if( ans == INF )
ans = -1;
return ans;
}
