#include <bits/stdc++.h>
#include "race.h"
using namespace std;
using ll = long long;
const int NMAX = 2e5;
const int INF = 1e9;
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];
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;
}
void updDist( int init, int node, int parent, int depth, ll sumEdges ) {
distSubtree[init].push_back( { sumEdges, depth } );
for( auto vec: edges[node] ) {
if( !is_removed[vec.first] && vec.first != parent )
updDist( init, vec.first, node, depth + 1, sumEdges + vec.second );
}
}
void decomposition( int node, int centroidParent ) {
int totalSz = calcSize( node, -1 );
int centroid = find_centroid( node, -1, totalSz );
is_removed[centroid] = true;
parent[centroid] = centroidParent;
updDist( centroid, centroid, -1, 0, 0 );
for( auto vec: edges[centroid] ) {
//cout << vec.first << " ";
if( !is_removed[vec.first] )
decomposition( vec.first, centroid );
}
}
int best_path( int n, int k, int h[][2], int len[] ) {
int i, st, dr, ans, mini, j, ind;
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 );
ans = INF;
for( i = 0; i < n; i++ ) {
sort( distSubtree[i].begin(), distSubtree[i].end(), [&]( pair<ll, int>& a, pair<ll, int>& b ) {
return a.first < b.first;
} );
ind = 0;
mini = INF;
for( j = 0; j < distSubtree[i].size() - 1; j++ ) {
mini = min( mini, distSubtree[i][j].second );
if( distSubtree[i][j].first != distSubtree[i][j+1].first ) {
distSubtree[i][ind++] = { distSubtree[i][j].first, mini };
mini = INF;
}
}
mini = min( mini, distSubtree[i][j].second );
distSubtree[i][ind++] = { distSubtree[i][j].first, mini };
st = 0;
dr = ind - 1;
while( st < dr ) {
while( distSubtree[i][st].first + distSubtree[i][dr].first > k )
dr--;
if( distSubtree[i][st].first + distSubtree[i][dr].first == k && st != dr )
ans = min( ans, distSubtree[i][st].second + distSubtree[i][dr].second );
st++;
}
}
if( ans == INF )
ans = -1;
return ans;
}
