#include "factories.h"
#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std ;
#define MAXN 500007
#define LOG 20
int n ;
vector < pair < int , int > > v[ MAXN ] ;
long long dist[ MAXN ] ;
int LCA[ MAXN ][ LOG + 1 ] ;
int lvl[ MAXN ] ;
int subtree[ MAXN ] ;
int lst[ MAXN ] ;
int used[ MAXN ] ;
int tot = 0 ;
long long ans[ MAXN ] ;
vector < int > ord ;
int fst[ MAXN ] ;
int dp[ 2 * MAXN ][ LOG + 3 ] ;
int pw_id[ 2 * MAXN ] ;
void init_lca ( ) {
int i , j ;
int sz = ord.size ( ) ;
for ( i = 1 ; i <= sz ; i ++ ) {
dp[ i ][ 0 ] = ord[ i - 1 ] ;
}
for ( j = 1 ; j <= LOG + 1 ; j ++ ) {
for ( i = 1 ; i + (1<<j) - 1 <= sz ; i ++ ) {
int nxt = i + (1<<(j-1)) ;
int u1 , u2 ;
u1 = dp[ i ][ j - 1 ] ;
u2 = dp[ nxt ][ j - 1 ] ;
if ( lvl[ u1 ] < lvl[ u2 ] ) { dp[ i ][ j ] = u1 ; }
else { dp[ i ][ j ] = u2 ; }
}
}
int val = 1 ;
int id = 0 ;
for ( i = 1 ; i <= sz ; i ++ ) {
while ( 2 * val < i ) { val *= 2 ; id ++ ; }
pw_id[ i ] = id ;
}
}
void precalc ( int vertex , int prv ) {
ord.push_back ( vertex ) ;
fst[ vertex ] = ord.size ( ) ;
int i ;
int sz = v[ vertex ].size ( ) ;
if ( prv != -1 ) {
for ( i = 1 ; i <= LOG ; i ++ ) {
LCA[ vertex ][ i ] = LCA[ LCA[ vertex ][ i - 1 ] ][ i - 1 ] ;
}
}
for ( i = 0 ; i < sz ; i ++ ) {
if ( v[ vertex ][ i ].first == prv ) { continue ; }
lvl[ v[ vertex ][ i ].first ] = lvl[ vertex ] + 1 ;
LCA[ v[ vertex ][ i ].first ][ 0 ] = vertex ;
dist[ v[ vertex ][ i ].first ] = dist[ vertex ] + v[ vertex ][ i ].second ;
precalc ( v[ vertex ][ i ].first , vertex ) ;
ord.push_back ( vertex ) ;
}
}
void dfs ( int vertex , int prv ) {
if ( used[ vertex ] == 1 ) { return ; }
tot ++ ;
int i ;
int sz = v[ vertex ].size ( ) ;
subtree[ vertex ] = 1 ;
for ( i = 0 ; i < sz ; i ++ ) {
if ( v[ vertex ][ i ].first == prv ) { continue ; }
if ( used[ v[ vertex ][ i ].first ] != 0 ) { continue ; }
dfs ( v[ vertex ][ i ].first , vertex ) ;
subtree[ vertex ] += subtree[ v[ vertex ][ i ].first ] ;
}
}
int find_centroid ( int vertex , int prv ) {
int i ;
int sz = v[ vertex ].size ( ) ;
for ( i = 0 ; i < sz ; i ++ ) {
if ( v[ vertex ][ i ].first == prv ) { continue ; }
if ( used[ v[ vertex ][ i ].first ] == 0 && subtree[ v[ vertex ][ i ].first ] > ( tot / 2 ) ) {
return find_centroid ( v[ vertex ][ i ].first , vertex ) ;
}
}
return vertex ;
}
void decompose ( int vertex , int prv ) {
tot = 0 ;
dfs ( vertex , -1 ) ;
int cen = find_centroid ( vertex , -1 ) ;
lst[ cen ] = prv ;
used[ cen ] = 1 ;
int i , sz ;
sz = v[ cen ].size ( ) ;
for ( i = 0 ; i < sz ; i ++ ) {
if ( used[ v[ cen ][ i ].first ] == 0 ) {
decompose ( v[ cen ][ i ].first , cen ) ;
}
}
}
int get_LCA ( int x , int y ) {
/**
int i ;
for ( i = LOG ; i >= 0 ; i -- ) {
if ( lvl[ x ] - (1<<i) >= lvl[ y ] ) {
x = LCA[ x ][ i ] ;
}
if ( lvl[ y ] - (1<<i) >= lvl[ x ] ) {
y = LCA[ y ][ i ] ;
}
}
for ( i = LOG ; i >= 0 ; i -- ) {
if ( LCA[ x ][ i ] != LCA[ y ][ i ] ) {
x = LCA[ x ][ i ] ;
y = LCA[ y ][ i ] ;
}
}
if ( x != y ) { x = LCA[ x ][ 0 ] ; }
return x ;
**/
if ( fst[ x ] > fst[ y ] ) { swap ( x , y ) ; }
int len = ( fst[ y ] - fst[ x ] + 1 ) ;
int val = pw_id[ len ] ;
int u1 = dp[ fst[ x ] ][ val ] ;
int u2 = dp[ fst[ y ] - (1<<val) + 1 ][ val ] ;
if ( lvl[ u1 ] < lvl[ u2 ] ) { return u1 ; }
return u2 ;
}
long long get_dist ( int x , int y ) {
int u = get_LCA ( x , y ) ;
return ( dist[ x ] + dist[ y ] - 2 * dist[ u ] ) ;
}
void update ( int vertex , int x ) {
while ( vertex != -1 ) {
long long cur = get_dist ( vertex , x ) ;
if ( ans[ vertex ] == -1 ) { ans[ vertex ] = cur ; }
if ( ans[ vertex ] > cur ) { ans[ vertex ] = cur ; }
vertex = lst[ vertex ] ;
}
}
void reset ( int vertex ) {
while ( vertex != -1 ) {
ans[ vertex ] = -1 ;
vertex = lst[ vertex ] ;
}
}
long long query ( int vertex ) {
long long ret = -1 ;
int st = vertex ;
while ( vertex != -1 ) {
if ( ans[ vertex ] > -1 ) {
long long cur = get_dist ( st , vertex ) + ans[ vertex ] ;
if ( ret == -1 ) { ret = cur ; }
if ( ret > cur ) { ret = cur ; }
}
vertex = lst[ vertex ] ;
}
return ret ;
}
void Init(int N, int A[], int B[], int D[]) {
n = N ;
int i ;
for ( i = 0 ; i < N - 1 ; i ++ ) {
A[ i ] ++ ;
B[ i ] ++ ;
v[ A[ i ] ].push_back ( make_pair ( B[ i ] , D[ i ] ) ) ;
v[ B[ i ] ].push_back ( make_pair ( A[ i ] , D[ i ] ) ) ;
}
precalc ( 1 , -1 ) ;
init_lca ( ) ;
decompose ( 1 , -1 ) ;
for ( i = 1 ; i <= n ; i ++ ) {
ans[ i ] = -1 ;
}
}
long long Query(int S, int X[], int T, int Y[]) {
int i ;
for ( i = 0 ; i < S ; i ++ ) {
X[ i ] ++ ;
}
for ( i = 0 ; i < T ; i ++ ) {
Y[ i ] ++ ;
}
for ( i = 0 ; i < S ; i ++ ) {
update ( X[ i ] , X[ i ] ) ;
}
long long ret = -1 ;
for ( i = 0 ; i < T ; i ++ ) {
long long cur = query ( Y[ i ] ) ;
if ( cur > -1 ) {
if ( ret == -1 ) { ret = cur ; }
if ( ret > cur ) { ret = cur ; }
}
}
for ( i = 0 ; i < S ; i ++ ) {
reset ( X[ i ] ) ;
}
return ret ;
}
