#include <bits/stdc++.h>
#include "race.h"
#define lp(i,a,b) for(int i=a;i<b;i++)
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
#define ll long long
#define sz size()
const int MAXN = 2e5+10 ;
using namespace std ;
int curTime ;
int ini[MAXN] , fim[MAXN] , pai[MAXN] , fatSomaVal[MAXN] , ta[MAXN] , resp[MAXN] ;
ll fatSomaKey[MAXN] , specialEdge[MAXN] ;
bool marc[MAXN] ;
vector< pair<int,ll> > adj[MAXN] ;
map<ll,int> mapa[MAXN] ;
map<ll,int>::iterator it ;
int bit[MAXN] ;
void add(int x) { for(int i = x ; i < MAXN ; i += (i&-i) ) bit[i] ++ ; }
int qry(int x)
{
int tot = 0 ;
for(int i = x ; i > 0 ; i -= (i&-i) )
tot += bit[i] ;
return tot ;
}
int get(int i , int j) { return qry(j) - qry(i) ; }
void dfs(int x)
{
ini[x] = ++ curTime ;
for( pair<int,ll> p : adj[x] )
if( ini[p.ff] == 0 )
{
pai[p.ff] = x ;
dfs(p.ff) ;
specialEdge[p.ff] = p.ss ;
}
fim[x] = curTime ;
}
void printMap(int idx)
{
printf("Printando o map do %d:\n" , idx ) ;
idx = ta[idx] ;
for(it = mapa[idx].begin() ; it != mapa[idx].end() ; it++ )
printf("%lld %d\n" , it->ff, it->ss) ;
printf("\n") ;
}
void inserta(int idx , ll Key , int Val)
{
if( mapa[idx].find(Val) == mapa[idx].end() )
mapa[idx].insert(mk(Key,Val)) ;
mapa[idx][Key] = min( mapa[idx][Key] , Val ) ;
}
int best_path(int n , int k , int h[][2] , int l[] )
{
lp(i,0,MAXN) resp[i] = MAXN ;
lp(i,0,n-1)
{
int a = h[i][0] , b = h[i][1] ;
adj[a].pb( mk( b , 1LL * l[i] ) ) ;
adj[b].pb( mk( a , 1LL * l[i] ) ) ;
}
dfs(0) ;
queue<int> q ;
lp(i,0,n)
if( ini[i] == fim[i] )
{
marc[i] = true ;
q.push(i) ;
ta[i] = q.sz ;
}
while( !q.empty() )
{
int davez = q.front() ;
q.pop() ;
marc[davez] = true ;
add(ini[davez]) ;
int father = pai[davez] ;
if( !marc[father] && get(ini[father] , fim[father]) == (fim[father]-ini[father]) )
{
q.push(father) ;
marc[father] = true ;
}
if( ini[davez] == fim[davez] ) continue ;
int bigChild = adj[davez][0].ff ;
if( bigChild == pai[davez] ) bigChild = adj[davez][1].ff ;
for(pair<int,ll> p : adj[davez])
if( mapa[ta[bigChild]].sz < mapa[ta[p.ff]].sz && p.ff != pai[davez] )
bigChild = p.ff ;
fatSomaKey[davez] = fatSomaKey[bigChild] + specialEdge[bigChild] ;
fatSomaVal[davez] = fatSomaVal[bigChild] + 1 ;
ta[davez] = ta[bigChild] ;
inserta( ta[davez] , specialEdge[bigChild] - fatSomaKey[davez] , 1 - fatSomaVal[davez] ) ;
if( mapa[ta[davez]].find(k-fatSomaKey[davez]) != mapa[ta[davez]].end() )
resp[davez] = mapa[ta[davez]][k-fatSomaKey[davez]] + fatSomaVal[davez] ;
for( pair<int,ll> p : adj[davez] )
{
int cur = p.ff ;
if( cur == bigChild || cur == pai[davez]) continue ;
vector<pair<ll,int> > atualiza ;
atualiza.pb( mk( specialEdge[cur] - fatSomaKey[davez] , 1- fatSomaVal[davez] ) ) ;
for(it = mapa[ta[cur]].begin() ; it != mapa[ta[cur]].end() ; it++ )
{
ll realKey = it->ff + fatSomaKey[cur] ;
int realVal = it->ss + fatSomaVal[cur] + 1 ;
ll updKey = realKey - fatSomaKey[davez] ;
int updVal = realVal - fatSomaVal[davez] ;
ll procuro = k - realKey - fatSomaKey[davez] ;
atualiza.pb(mk(updKey , updVal)) ;
if( k == realKey ) resp[davez] = min( resp[davez] , realVal ) ;
if( mapa[ta[davez]].find(procuro) == mapa[ta[davez]].end() )
continue ;
resp[davez] = min(resp[davez] , mapa[ta[davez]][procuro] + fatSomaVal[davez] + realVal - 1) ;
}
for(pair<ll,int> p : atualiza)
inserta(ta[davez], p.ff , p.ss ) ;
}
}
int ans = *min_element(resp, resp+n) ;
return ans == MAXN ? -1 : ans ;
}
