#include <bits/stdc++.h>
#define DIM 200010
#define INF 2000000000
//#include "race.h"
using namespace std;
vector <pair<int,int> > L[DIM];
pair <int,int> rmq[20][DIM*4],poz[DIM];
int level[DIM],fth[DIM],first[DIM],p[DIM*4],E[DIM],euler[DIM*4],dist[DIM];
int k,el,sol;
struct treap{
int val;
int priority;
int nr;
int lazy;
treap *left;
treap *right;
treap (int val, int priority, int nr, int lazy, treap *left, treap *right){
this->val = val;
this->priority = priority;
this->nr = nr;
this->lazy = lazy;
this->left = left;
this->right = right;
}
};
treap *rad, *nil;
int get_random (){
return rand()%(INF-1)+1;
}
treap* update (treap *rad){
if (rad == nil)
rad->nr = 0;
else {
rad->nr = rad->left->nr + rad->right->nr + 1;
if (rad->lazy){
if (rad->left != nil){
rad->left->val += rad->lazy;
rad->left->lazy += rad->lazy;
}
if (rad->right != nil){
rad->right->val += rad->lazy;
rad->right->lazy += rad->lazy;
}
rad->lazy = 0;
}}
return rad;
}
pair <treap*, treap*> split (treap *rad, int poz){
rad = update (rad);
pair <treap*, treap*> ans;
if (rad == nil)
return make_pair(nil,nil);
if (rad->left->nr + 1 > poz){
ans = split (rad->left,poz);
rad->left = ans.second;
ans.second = rad;
} else {
ans = split (rad->right, poz - rad->left->nr - 1);
rad->right = ans.first;
ans.first = rad;
}
rad = update (rad);
return ans;
}
treap* join (treap *rad1, treap *rad2){
if (rad1 == nil)
return rad2;
if (rad2 == nil)
return rad1;
rad1 = update (rad1);
rad2 = update (rad2);
if (rad->priority > rad2->priority){
rad1->right = join (rad1->right,rad2);
rad1 = update (rad1);
return rad1;
} else {
rad2->left = join (rad1,rad2->left);
rad2 = update (rad2);
return rad2;
}
return nil;
}
treap* _insert (treap *rad, int poz, int val){
if (rad == nil){
rad = new treap (val,get_random(),1,0,nil,nil);
rad = update (rad);
return rad;
}
pair <treap*, treap*> aux = split (rad,poz-1);
rad = new treap (val,get_random(),1,0,aux.first,aux.second);
rad = update (rad);
return rad;
}
int get_lca (int x, int y){
int posx = first[x], posy = first[y];
if (posx > posy)
swap (posx,posy);
int nr = p[posy-posx+1];
pair <int,int> sol = min (rmq[nr][posx],rmq[nr][posy-(1<<nr)+1]);
return euler[sol.second];
}
int get_dist (int x, int y){
int lca = get_lca (x,y);
return level[x] + level[y] - 2*level[lca];
}
void update_interval (int x, int y, int val){
if (x > y)
return;
/// fac += val la toate pozitiile intre x si y
pair <treap*, treap*> aux = split (rad,y);
pair <treap*, treap*> aux2 = split (aux.first,x-1);
aux2.second->val += val;
aux2.second->lazy += val;
aux.first = join (aux2.first,aux2.second);
rad = join (aux.first,aux.second);
rad = update (rad);
}
void _search (treap *&rad, int val, int poz, int nod){
rad = update (rad);
if (rad == nil)
return;
if (rad->val < val){
/// clar trb sa ma duc in dreapta
_search (rad->right,val,poz + rad->left->nr + 1, nod);
} else {
if (rad->val > val)
_search (rad->left,val,poz,nod);
else { /// rad->val == val
sol = min (sol,get_dist(E[poz + rad->left->nr + 1],nod));
if (rad->left->val == val)
_search (rad->left,val,poz,nod);
if (rad->right->val == val)
_search (rad->right,val,poz + rad->left->nr + 1, nod);
}}}
void dfs (int nod, int tata){
level[nod] = 1 + level[tata];
fth[nod] = tata;
E[++k] = nod;
poz[nod].first = k;
/// euler pt lca
euler[++el] = nod;
first[nod] = el;
for (auto it : L[nod]){
if (it.first != tata){
dist[it.first] = it.second + dist[nod];
dfs (it.first,nod);
euler[++el] = nod;
}
}
poz[nod].second = k;
}
void afisare (treap *&rad, int poz){
rad = update (rad);
if (rad == nil)
return;
cout<<rad->val<<" "<<poz+rad->left->nr+1<<"\n";
afisare (rad->left,poz);
afisare (rad->right,poz+rad->left->nr+1);
}
void dfs2 (int nod, int tata, int cost, int k, int n){
if (nod != 1){
update_interval (1,poz[nod].first-1,cost);
update_interval (poz[nod].first,poz[nod].second,-cost);
update_interval (poz[nod].second+1,n,cost);
}
//if (nod == 2){
// afisare (rad,0);
//}
_search (rad,k,0,nod);
for (auto it : L[nod])
if (it.first != tata)
dfs2 (it.first,nod,it.second,k,n);
/// am terminat cu nod, trb sa refarc distantele
update_interval (1,poz[nod].first-1,-cost);
update_interval (poz[nod].first,poz[nod].second,cost);
update_interval (poz[nod].second+1,n,-cost);
}
int best_path (int n, int k, int h[][2], int l[]){
int i,j,x,y;
for (i=0;i<n-1;i++){
x = h[i][0]+1, y = h[i][1]+1;
L[x].push_back(make_pair(y,l[i]));
L[y].push_back(make_pair(x,l[i]));
}
dfs (1,0);
/// build lca
for (i=1;i<=el;i++)
rmq[0][i] = make_pair (level[euler[i]],i);
for (i=1;(1<<i)<=el;i++)
for (j=1;j<=el;j++){
rmq[i][j] = rmq[i-1][j];
if (j + (1<<(i-1)) <= el && rmq[i-1][j + (1<<(i-1))].first < rmq[i][j].first)
rmq[i][j] = rmq[i-1][j + (1<<(i-1))];
}
for (i=2;i<=el;i++)
p[i] = p[i/2] + 1;
srand(time(0));
rad = nil = new treap (0,0,0,0,NULL,NULL);
for (i=1;i<=n;i++)
rad = _insert (rad,i,dist[i]);
sol = INF;
dfs2 (1,0,0,k,n);
if (sol != INF)
return sol;
return -1;
}
