#pragma GCC optimize ("Ofast", "unroll-loops")
#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
using namespace std;
const int NMAX = 2e5;
const int INF = 1e9;
using ll = long long;
struct muchii {
int nod, cost;
};
vector <vector <muchii>> adj;
int n, k;
struct noduri{
int parent = -1;
int weight = 1; ///al subarborelui
int lant;
ll dist = 0; ///de la 0 la nod
int depth = 0; ///basically CATE muchii de la 0 la nod
}v[NMAX + 2];
int cnt = 0; ///cate lanturi
void dfsbuild(int start) {
bool ok = 0;
for(auto x : adj[start]) {
if(x.nod == v[start].parent)
continue;
ok = 1;
v[x.nod].parent = start;
v[x.nod].dist = v[start].dist + x.cost;
v[x.nod].depth = v[start].depth + 1;
dfsbuild(x.nod);
v[start].weight += v[x.nod].weight;
}
///formam lanturile
if(!ok) { ///frunza, lant nou
cnt++;
v[start].lant = cnt;
return;
}
int maxx = 0, chain = 0;
for(auto x : adj[start]) {
if(x.nod == v[start].parent)
continue;
if(v[x.nod].weight > maxx) {
maxx = v[x.nod].weight;
chain = v[x.nod].lant;
}
}
v[start].lant = chain;
}
vector <map <ll, int>> umap; ///pt fiec lant
int ans = INF;
void solve(int start) {
for(auto x : adj[start]) { ///prima oara fiul heavy
if(x.nod != v[start].parent && v[x.nod].lant == v[start].lant) {
solve(x.nod);
break;
}
}
for(auto x : adj[start]) {
if(x.nod == v[start].parent || v[x.nod].lant == v[start].lant)
continue;
solve(x.nod);
///Small to large guys
if(umap[v[start].lant].size() < umap[v[x.nod].lant].size())
swap(umap[v[start].lant], umap[v[x.nod].lant]);
///Step 1) pt fiec fiu light, faci query cu lantul mare
for(auto var : umap[v[x.nod].lant]) {
ll caut = k + 2 * v[start].dist - var.first;
if(umap[v[start].lant].find(caut) != umap[v[start].lant].end()) {
ans = min(ans, var.second + umap[v[start].lant][caut] -
2 * v[start].depth);
}
}
///Step 2) pt fiec fiu light, adaugi in map-ul lantului mare
for(auto var : umap[v[x.nod].lant]) {
if(umap[v[start].lant].find(var.first) != umap[v[start].lant].end())
umap[v[start].lant][var.first] = min(umap[v[start].lant][var.first], var.second);
else
umap[v[start].lant][var.first] = var.second;
}
umap[v[x.nod].lant].clear();
}
///query ca lantul poate se termina in el
if(umap[v[start].lant].find(v[start].dist + k) != umap[v[start].lant].end())
ans = min(ans, umap[v[start].lant][v[start].dist + k] - v[start].depth);
///la FINAL adaugam si nr nostru
if(umap[v[start].lant].find(v[start].dist) != umap[v[start].lant].end())
umap[v[start].lant][v[start].dist] = min(umap[v[start].lant][v[start].dist],
v[start].depth);
else
umap[v[start].lant][v[start].dist] = v[start].depth;
}
int best_path(int N, int K, int h[NMAX][2], int l[NMAX]) {
n = N, k = K;
adj.resize(n + 1);
for(int i = 0; i < n - 1; i++) {
adj[h[i][0]].push_back({h[i][1], l[i]});
adj[h[i][1]].push_back({h[i][0], l[i]});
}
dfsbuild(0);
/*for(int i = 0; i < n; i++)
cout << v[i].parent << " " << v[i].weight << " " << v[i].lant << " "
<< v[i].dist << " " << v[i].depth << '\n';*/
umap.resize(cnt + 1);
solve(0);
if(ans == INF)
ans = -1;
return ans;
}
