#include "factories.h"
#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std ;
#define MAXN 500007
int n ;
vector < pair < int , int > > v[ MAXN ] ;
long long dist[ MAXN ] ;
int subtree[ MAXN ] ;
int lvl[ MAXN ] ;
int heavy[ MAXN ] ;
int root[ MAXN ] ;
int pos_in_tree[ MAXN ] ;
int lst[ MAXN ] ;
int rev[ MAXN ] ;
long long inf ;
class Tree {
public :
long long tr[ 3 * MAXN ] ;
long long u[ 3 * MAXN ] ;
long long lazy[ 3 * MAXN ] ;
void init ( int where , int IL , int IR ) {
lazy[ where ] = 0 ;
u[ where ] = inf ;
if ( IL == IR ) {
tr[ where ] = -2 * dist[ rev[ IL ] ] ;
return ;
}
int mid = ( IL + IR ) / 2 ;
init ( 2 * where , IL , mid ) ;
init ( 2 * where + 1 , mid + 1 , IR ) ;
tr[ where ] = min ( tr[ 2 * where ] , tr[ 2 * where + 1 ] ) ;
}
void push_lazy ( int where , int IL , int IR ) {
if ( lazy[ where ] == 0 ) { return ; }
if ( lazy[ where ] > 0 ) {
u[ where ] = min ( u[ where ] , tr[ where ] + lazy[ where ] ) ;
if ( IL != IR ) {
if ( lazy[ 2 * where ] < 0 ) { lazy[ 2 * where ] = 0 ; }
if ( lazy[ 2 * where + 1 ] < 0 ) { lazy[ 2 * where + 1 ] = 0 ; }
if ( lazy[ 2 * where ] == 0 ) { lazy[ 2 * where ] = lazy[ where ] ; }
if ( lazy[ 2 * where + 1 ] == 0 ) { lazy[ 2 * where + 1 ] = lazy[ where ] ; }
lazy[ 2 * where ] = lazy[ where ] ;
lazy[ 2 * where + 1 ] = lazy[ where ] ;
}
lazy[ where ] = 0 ;
}
else {
u[ where ] = inf ;
if ( IL != IR ) {
lazy[ 2 * where ] = -1 ;
lazy[ 2 * where + 1 ] = -1 ;
}
lazy[ where ] = 0 ;
}
}
void update ( int where , int IL , int IR , int CURL , int CURR , long long val ) {
push_lazy ( where , IL , IR ) ;
if ( IR < CURL || CURR < IL ) { return ; }
if ( CURL <= IL && IR <= CURR ) {
lazy[ where ] = val ;
if ( val < 0 ) { lazy[ where ] = -1 ; }
push_lazy ( where , IL , IR ) ;
return ;
}
int mid = ( IL + IR ) / 2 ;
update ( 2 * where , IL , mid , CURL , CURR , val ) ;
update ( 2 * where + 1 , mid + 1 , IR , CURL , CURR , val ) ;
u[ where ] = min ( u[ 2 * where ] , u[ 2 * where + 1 ] ) ;
}
long long query ( int where , int IL , int IR , int CURL , int CURR ) {
push_lazy ( where , IL , IR ) ;
if ( IR < CURL || CURR < IL ) { return inf ; }
if ( CURL <= IL && IR <= CURR ) {
return u[ where ] ;
}
int mid = ( IL + IR ) / 2 ;
return min ( query ( 2 * where , IL , mid , CURL , CURR ) , query ( 2 * where + 1 , mid + 1 , IR , CURL , CURR ) ) ;
}
};
Tree w ;
void dfs ( int vertex , int prv ) {
printf ( "dist[ %d ] = %lld\n" , vertex , dist[ vertex ] ) ;
int i ;
int sz = v[ vertex ].size ( ) ;
subtree[ vertex ] = 1 ;
int mx , id ;
mx = id = 0 ;
for ( i = 0 ; i < sz ; i ++ ) {
if ( v[ vertex ][ i ].first == prv ) { continue ; }
lst[ v[ vertex ][ i ].first ] = vertex ;
lvl[ v[ vertex ][ i ].first ] = lvl[ vertex ] + 1 ;
dist[ v[ vertex ][ i ].first ] = dist[ vertex ] + v[ vertex ][ i ].second ;
dfs ( v[ vertex ][ i ].first , vertex ) ;
subtree[ vertex ] += subtree[ v[ vertex ][ i ].first ] ;
if ( subtree[ v[ vertex ][ i ].first ] > mx ) {
mx = subtree[ v[ vertex ][ i ].first ] ;
id = v[ vertex ][ i ].first ;
}
}
heavy[ vertex ] = id ;
}
void decompose ( int vertex , long long val ) {
while ( vertex != 0 ) {
int st = root[ vertex ] ;
w.update ( 1 , 1 , n , pos_in_tree[ st ] , pos_in_tree[ vertex ] , val ) ;
vertex = lst[ st ] ;
}
}
long long calc ( int vertex ) {
long long ret = inf ;
long long add = dist[ vertex ] ;
while ( vertex != 0 ) {
int st = root[ vertex ] ;
ret = min ( ret , w.query ( 1 , 1 , n , pos_in_tree[ st ] , pos_in_tree[ vertex ] ) ) ;
vertex = lst[ st ] ;
}
ret += add ;
return ret ;
}
void Init(int N, int A[], int B[], int D[]) {
n = N ;
int i , j ;
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 ] ) ) ;
}
dfs ( 1 , -1 ) ;
int id = 0 ;
for ( i = 1 ; i <= n ; i ++ ) {
if ( i == 1 || heavy[ lst[ i ] ] != i ) {
j = i ;
while ( j != 0 ) {
root[ j ] = i ;
id ++ ;
pos_in_tree[ j ] = id ;
rev[ id ] = j ;
j = heavy[ j ] ;
}
}
}
inf = 1 ;
for ( i = 1 ; i <= 16 ; i ++ ) {
inf *= 10 ;
}
w.init ( 1 , 1 , n ) ;
}
long long Query(int S, int X[], int T, int Y[]) {
int i ;
for ( i = 0 ; i < S ; i ++ ) {
X[ i ] ++ ;
decompose ( X[ i ] , dist[ X[ i ] ] ) ;
}
long long ret = inf ;
for ( i = 0 ; i < T ; i ++ ) {
Y[ i ] ++ ;
ret = min ( ret , calc ( Y[ i ] ) ) ;
}
for ( i = 0 ; i < S ; i ++ ) {
decompose ( X[ i ] , -dist[ X[ i ] ] ) ;
}
return ret ;
}
