#include <bits/stdc++.h>
#include "race.h"
#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
#define fora(i, a, b) for(int i = int(a); i >= int(b); -- i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
const int lim = 2e5;
const int ultimonivel = log2(lim);
int n, root, res = -1, k;
vi centroidtree[lim];
vector<pii> tree[lim];
bool centroid[lim];
int subtree_size[lim];
bool visited[lim];
pii p[lim];
map<int, pair<int, vi>> val[lim];
queue<int> qvisited;
queue<int> qsubtree;
vi ancestros[lim];
int profundidad[lim];
void dfslac(int u) {
visited[u] = 1;
qvisited.push(u);
for(pii & v : tree[u]){
if(!visited[v.fi]){
p[v.fi] = mp(u, v.se);
profundidad[v.fi] = profundidad[u] + 1;
dfslac(v.fi);
}
}
}
void armarlca(){
forn(i, 0, n - 1){
if(p[i].fi != i){
ancestros[i].pb(p[i].fi);
}
}
forn(j, 1, ultimonivel){
forn(i, 0, n - 1){
if((int) ancestros[i].size() >= j){
if((int) ancestros[ancestros[i][j - 1]].size() >= j) {
ancestros[i].pb(ancestros[ancestros[i][j - 1]][j - 1]);
}
}
}
}
}
int lca(int u, int v){
if(profundidad[u] > profundidad[v]){
swap(u, v);
}
fora(i, ultimonivel, 0){
if(profundidad[v] - (1 << i) >= profundidad[u]){
v = ancestros[v][i];
}
}
if(u == v){
return u;
}
fora(i, ultimonivel, 0){
if(profundidad[u] >= (1 << i)){
if(ancestros[v][i] != ancestros[u][i]){
v = ancestros[v][i];
u = ancestros[u][i];
}
}
}
return ancestros[u][0];
}
void dfs(int u, int & nodes) {
qvisited.push(u);
visited[u] = 1;
nodes ++;
subtree_size[u] = 1;
qsubtree.push(u);
for(pii & v : tree[u]){
if(!visited[v.fi] && !centroid[v.fi]) {
dfs(v.fi, nodes);
subtree_size[u] += subtree_size[v.fi];
}
}
}
int getcentroid(int u, int nodes) {
qvisited.push(u);
visited[u] = 1;
for(pii & v : tree[u]) {
if(!visited[v.fi] && !centroid[v.fi] && subtree_size[v.fi] > nodes / 2){
return getcentroid(v.fi, nodes);
}
}
return u;
}
void limpiarsubtree() {
int act;
while(!qsubtree.empty()){
act = qsubtree.front();
qsubtree.pop();
subtree_size[act] = 0;
}
}
void limpiarvisited() {
int act;
while(!qvisited.empty()){
act = qvisited.front();
qvisited.pop();
visited[act] = 0;
}
}
int decomposicion (int u) {
limpiarsubtree();
limpiarvisited();
int nodes = 0;
dfs(u, nodes);
limpiarvisited();
int centroidact = getcentroid(u, nodes);
centroid[centroidact] = 1;
int sig;
for(pii & v : tree[centroidact]) {
if(!centroid[v.fi]){
sig = decomposicion(v.fi);
centroidtree[centroidact].pb(sig);
centroidtree[sig].pb(centroidact);
}
}
return centroidact;
}
void resolucion(int u) {
visited[u] = 1;
int aux, aux2, aux3, aux4;
set<int> modificar;
int suma;
for(int & v : centroidtree[u]) {
if(!visited[v]){
suma = 0;
///cout << u << "->" << v << "\n";
resolucion(v);
aux = lca(u, v);
aux2 = v;
while(aux2 != aux){
suma += p[aux2].se;
aux2 = p[aux2].fi;
if(aux2 != aux){
modificar.insert(aux2);
}
}
aux2 = u;
while(aux2 != aux){
suma += p[aux2].se;
aux2 = p[aux2].fi;
if(aux2 != aux){
modificar.insert(aux2);
}
}
cout << u << "->" << v << " " << suma << "\n";
if(aux != u && aux != v){
modificar.insert(aux);
}
for(auto j : val[v]){
for(int & x : j.se.se){
if(modificar.count(x)){
aux4 = suma - j.fi;
}
else{
aux4 = suma + j.fi;
}
if(val[u].count(k - aux4)){
aux3 = lca(x, u);
if(res == -1){
res = val[u][k - aux4].fi + (profundidad[x] - profundidad[aux3]) + (profundidad[u] - profundidad[aux3]);
}
res = min(res, val[u][k - aux4].fi + (profundidad[x] - profundidad[aux3]) + (profundidad[u] - profundidad[aux3]));
}
}
}
if(val[u].count(k - suma)){
aux3 = lca(v, u);
if(res == -1){
res = val[u][k - suma].fi + (profundidad[v] - profundidad[aux3]) + (profundidad[u] - profundidad[aux3]);
}
res = min(res, val[u][k - suma].fi + (profundidad[v] - profundidad[aux3]) + (profundidad[u] - profundidad[aux3]));
}
for(auto j : val[v]){
for(int & x : j.se.se){
if(modificar.count(x)){
aux4 = suma - j.fi;
}
else{
aux4 = suma + j.fi;
}
aux3 = lca(x, u);
if(!val[u].count(aux4)){
val[u][aux4].fi = (profundidad[x] - profundidad[aux3]) + (profundidad[u] - profundidad[aux3]);
}
val[u][aux4].fi = min(val[u][aux4].fi, (profundidad[x] - profundidad[aux3]) + (profundidad[u] - profundidad[aux3]));
val[u][aux4].se.pb(x);
}
}
aux3 = lca(v, u);
if(!val[u].count(suma)){
val[u][suma].fi = (profundidad[v] - profundidad[aux3]) + (profundidad[u] - profundidad[aux3]);
}
val[u][suma].fi = min(val[u][suma].fi, (profundidad[v] - profundidad[aux3]) + (profundidad[u] - profundidad[aux3]));
val[u][suma].se.pb(v);
}
}
}
int best_path(int N, int K, int H[][2], int L[]){
n = N;
forn(i, 0, n - 2){
tree[H[i][0]].pb(mp(H[i][1], L[i]));
tree[H[i][1]].pb(mp(H[i][0], L[i]));
}
k = K;
p[0] = mp(0, 0);
dfslac(0);
armarlca();
limpiarvisited();
root = decomposicion(0);
limpiarvisited();
resolucion(root);
/**forn(i, 0, n - 1){
cout << i << " Diferentes val:\n";
for(auto it : val[i]){
cout << it.fi << "\n";
}
}*/
return res;
}
