/*
Author: Nguyen Chi Thanh - High School for the Gifted - VNU.HCM (i2528)
*/
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
/* START OF TEMPALTE */
// #define int long long
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define popcount __builtin_popcountll
#define all(x) (x).begin(), (x).end()
#define BIT(x, i) (((x) >> (i)) & 1)
#define MASK(x) (1ll << (x))
#define SZ(a) ((int32_t)a.size())
#define debug(a, l, r) {for (int _i = (l); _i <= (r); ++_i) cout << (a)[_i] << ' '; cout << '\n';}
template<class X, class Y>
bool minimize(X &x, const Y &y) {
if (x > y) {
x = y;
return true;
} else return false;
}
template<class X, class Y>
bool maximize(X &x, const Y &y) {
if (x < y) {
x = y;
return true;
} else return false;
}
/* END OF TEMPALTE */
const int MAXN = 2e5 + 5;
const int INF = (int)1e9 + 7;
int n, k, sz[MAXN], res = INF;
vector<pii> adj[MAXN];
bitset<MAXN> active;
void computeSubtreeSize(int u, int par = 0) {
sz[u] = 1;
for (auto &e : adj[u]) {
int v = e.fi;
if (v == par || !active[v]) continue;
computeSubtreeSize(v, u);
sz[u] += sz[v];
}
}
int findCentroid(int u, int numNode, int par = 0) {
for (auto &e : adj[u]) {
int v = e.fi;
if (v == par || !active[v]) continue;
if (sz[v] > numNode / 2)
return findCentroid(v, numNode, u);
}
return u;
}
void getDepths(int u, int curHeight, ll curDepth, vector<pair<ll, int>> &depths, int par = 0) {
if (curDepth > k) return;
depths.push_back({curDepth, curHeight});
for (auto &e : adj[u]) {
int v = e.fi, w = e.se;
if (v == par || !active[v]) continue;
getDepths(v, curHeight + 1, curDepth + w, depths, u);
}
}
void centroidDecomposition(int u) {
computeSubtreeSize(u);
int centroid = findCentroid(u, sz[u]);
active[centroid] = 0;
vector<pair<ll, int>> depths;
map<int, int> mp;
mp[0] = 0;
for (auto &e : adj[centroid]) {
int v = e.fi, w = e.se;
if (!active[v]) continue;
depths.clear();
getDepths(v, 1, w, depths, centroid);
// cout << v << ":\n";
// for (auto x : depths) cout << x.fi << ' ' << x.se << '\n';
for (auto x : depths) {
ll depth = x.fi; int height = x.se;
if (mp.count(k - depth)) {
minimize(res, mp[k - depth] + height);
}
if (mp.count(depth)) minimize(mp[depth], height);
else mp[depth] = height;
}
}
for (auto &e : adj[centroid]) {
int v = e.fi;
if (active[v]) centroidDecomposition(v);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N; k = K;
for (int i = 0; i < n - 1; ++i) {
int u = H[i][0] + 1, v = H[i][1] + 1, w = L[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
active.set();
centroidDecomposition(1);
return (res == INF ? -1 : res);
}
// #ifdef NCTHANH
// int N, K, H[MAXN][2], L[MAXN];
// void solve() {
// cin >> N >> K;
// for (int i = 0; i < N - 1; ++i) {
// cin >> H[i][0] >> H[i][1];
// }
// for (int i = 0; i < N - 1; ++i) cin >> L[i];
// cout << best_path(N, K, H, L);
// }
// signed main() {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// ios_base::sync_with_stdio(0);
// cin.tie(nullptr); cout.tie(nullptr);
// solve();
// return 0;
// }
// #endif
