#include <bits/stdc++.h>
#include "race.h"
using namespace std;
using ll = long long;
#define int ll
#define sz(x) (x).size()
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
const int nmax = 2e5 + 5, vmax = 1e6 + 5, inf = 1e9 + 5;
struct MN {
int x, atr;
MN(int a = inf, int b = -1): x(a), atr(b) {;}
MN operator += (const MN& a) {
//if(a.atr == atr)
#warning idk
x = min(x, a.x);
return *this;
}
};
struct MN2 {
MN a, b;
MN2(MN x = MN(), MN y = MN()): a(x), b(y) {;}
MN2 operator += (const MN& x) {
if(x.x < a.x) {
if(x.atr == a.atr)
a.x = x.x;
else {
b = a;
a = x;
}
}
else if(x.x < b.x && x.atr != a.atr) {
b = x;
}
return *this;
}
int operator()(const MN& x) const {
return x.x + (x.atr == a.atr? b.x : a.x);
}
};
vector<pii> g[nmax];
int K;
int mn = nmax;
namespace Centr {
MN2 freq[vmax];
vector<tii> lst;
int area[nmax];
int occ[nmax];
void init(int node, int f) {
area[node] = 0;
if(occ[node] == 1) return;
for(auto [x, e] : g[node]) {
if(x != f)
init(x, node),
area[node] += area[x];
}
area[node]++;
return;
}
int findcentr(int node, int f, int thresh) {
for(auto [x, e] : g[node]) {
if(x == f) continue;
if(occ[x] == 0 && area[x] > thresh) {
return findcentr(x, node, thresh);
}
}
return node;
}
void dfs(int node, int f, int atr, int dist, int h = 1) {
if(dist > K) return;
if(occ[node] == 1) return;
lst.emplace_back(dist, h, atr);
//cerr << node << ' ' << ' ' << f << ' ' << atr << ' ' << dist << ' ' << h << '\n';
for(auto [x, e] : g[node]) {
if(x == f) continue;
dfs(x, node, atr, dist + e, h + 1);
}
}
void decomp(int node) {
init(node, node);
//cerr << area[node] << ' ';
node = findcentr(node, node, area[node] / 2);
//cerr<< area[node] << ' ' << node << '\n';
lst.clear();
lst.emplace_back(0, 0, node);
for(auto [x, e] : g[node]) {
dfs(x, node, x, e);
}
//cerr << node << ":\n";
for(auto [ptr, val, atr] : lst) {
//cerr << ptr << ' ' << val << ' ' << atr << '\n';
freq[ptr] += MN(val, atr);
}
for(auto [ptr, val, atr] : lst) {
mn = min(mn, freq[K - ptr](MN(val, atr)));
}
for(auto [ptr, var, atr] : lst) {
freq[ptr] = MN2();
}
occ[node] = 1;
//cerr << "-------\n";
for(auto [x, e] : g[node]) {
if(occ[x] != 1)
decomp(x);
}
return;
}
}
signed best_path(signed n, signed k, signed H[][2], signed L[]) {
K = k;
for(int i = 0; i < n - 1; i++)
g[H[i][0]].emplace_back(H[i][1], L[i]),
g[H[i][1]].emplace_back(H[i][0], L[i]);
Centr::lst.reserve(n);
Centr::decomp(0);
if(mn == nmax) return -1;
return mn;
}
