// time-limit: 3000
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
void setIO(string File_name) {
cin.tie(0)->sync_with_stdio(0);
if (File_name.size()) {
freopen((File_name + ".in").c_str(), "r", stdin);
freopen((File_name + ".out").c_str(), "w", stdout);
}
}
class CD {
private:
vector<vector<pair<int, int>>> tree;
vector<int> sub;
vector<bool> rem;
gp_hash_table<int, pair<int, int>> mp;
int ans = -1;
int k;
int dfs(int u, int p) {
sub[u] = 1;
for (auto [v, w] : tree[u]) {
if (!rem[v] && v != p) {
sub[u] += dfs(v, u);
}
}
return sub[u];
}
int dfs(int u, int p, int n) {
for (auto [v, w] : tree[u]) {
if (!rem[v] && v != p && sub[v] > n / 2) {
return dfs(v, u, n);
}
}
return u;
}
void process(int u, int p, int depth, long long sum, bool filling, int c) {
int need = k - sum;
if (need < 0) return;
if (filling) {
if (mp.find(sum) == mp.end() || mp[sum].second != c) {
mp[sum] = {depth, c};
}
else {
mp[sum].first = min(mp[sum].first, depth);
}
}
else if (mp.find(need) != mp.end() && mp[need].second == c) {
if (ans == -1) {
ans = depth + mp[need].first;
}
else if (depth + mp[need].first < ans) {
ans = depth + mp[need].first;
}
}
for (auto [v, w] : tree[u]) {
if (v != p && !rem[v]) {
process(v, u, depth + 1, sum + w, filling, c);
}
}
}
void build(int u, int p) {
int n = dfs(u, p);
int c = dfs(u, p, n);
rem[c] = true;
mp[0] = {0, c};
for (auto [v, w] : tree[c]) {
if (!rem[v]) {
process(v, c, 1, w, 0, c);
process(v, c, 1, w, 1, c);
}
}
for (auto [v, w] : tree[c]) {
if (!rem[v]) {
build(v, u);
}
}
}
public:
CD(const vector<vector<pair<int, int>>>& t, int k_) {
int n = t.size();
sub.resize(n);
rem.resize(n);
tree = t;
k = k_;
build(0, -1);
}
int solve() {
return ans;
}
};
struct edge {
int u, v, w;
};
int best_path(int n, int k, int h[][2], int* l) {
vector<edge> E(n - 1);
for (int i = 0; i < n - 1; i++) {
int u = h[i][0], v = h[i][1];
E[i] = {u, v, -1};
}
for (int i = 0; i < n - 1; i++) {
int ll = l[i];
E[i].w = ll;
}
vector<vector<pair<int, int>>> t(n);
for (auto e : E) {
t[e.u].push_back({e.v, e.w});
t[e.v].push_back({e.u, e.w});
}
CD g(t, k);
return g.solve();
}
