#include <bits/stdc++.h>
#include "race.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
#define FOR(i,a) for (int i=0; i<(a); i++)
#define FORI(i,a,b) for (int i=a; i<(b); i++)
#define FORd(i,a) for (int i=(a)-1; i>=0; i--)
#define FORId(i,a,b) for (int i=(a)-1; i>=(b); i--)
#define trav(a,x) for (auto& a : x)
#define uid(a,b) uniform_int_distribution<int>(a, b)(rng)
#define printv(i,x) trav(i,x) cout << i << " "; cout << "\n";
#define sz(x) (int) (x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert
#define LEFT(x) (2*x)
#define RIGHT(x) (2*x+1)
const int MOD = 998244353;
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
#define MAX 100000
int num_of_vertices,kilometers;
vi edges[MAX], costs[MAX];
vector<set<ll>> sumk(MAX);
vector<map<ll,int>> highway(MAX);
vi sub_size(MAX);
int ans, mini = INF;
void p(int u, ll cost, int qnts, int ant)
{
// cout << u << " " << ant << "\n";
int maxi = -1, qual = -1;
FOR(i,sz(edges[u]))
{
int v = edges[u][i];
int w = costs[u][i];
if (v == ant) continue;
p(v,cost+w,qnts+1,u);
if (sub_size[v] > maxi)
{
maxi = sub_size[v];
qual = v;
}
}
// cout << u << " " << ant << ":\n";
// cout << qual << " " << maxi << "\n";
if (qual != -1)
{
swap(sumk[u],sumk[qual]); // O(1)
swap(highway[u],highway[qual]);
sub_size[u] = sub_size[qual];
// Query
if (sumk[u].count(kilometers+cost))
mini = min(mini,highway[u][kilometers+cost]-qnts);
// Update
if (sumk[u].count(cost) == 0)
sumk[u].insert(cost);
highway[u][cost] = qnts;
sub_size[u]++;
FOR(i,sz(edges[u]))
{
int v = edges[u][i];
if (v == qual or v == ant) continue;
for (auto j : sumk[v])
{
// Queries
if (sumk[u].count(kilometers-(j-cost)+cost))
mini = min(mini,highway[u][kilometers-(j-cost)+cost]-qnts + highway[v][j]-qnts);
}
for (auto j : sumk[v])
{
// Updates
if (sumk[u].count(j) == 0)
sumk[u].insert(j);
highway[u][j] = highway[v][j];
sub_size[u]++;
}
}
}
else
{
sub_size[u] = 1;
sumk[u].insert(cost);
highway[u][cost] = qnts;
if (sumk[u].count(kilometers))
mini = min(mini,qnts);
}
// cout << "mini: " << mini << "\n";
// cout << "sumk de " << u << ": ";
// for (auto i : sumk[u])
// cout << i << " ";
// cout << "\n";
// cout << "highway de " << u << ": ";
// for (auto i : highway[u])
// cout << i.f << ": " << i.s << " | ";
// cout << "\n";
}
int best_path(int n, int k, int (*h)[2], int* l)
{
FOR(i,n-1)
{
edges[i].clear();
costs[i].clear();
sumk[i].clear();
highway[i].clear();
sub_size[i] = 0;
mini = INF;
}
FOR(i,n-1)
{
ll u, v, w;
u = h[i][0];
v = h[i][1];
w = l[i];
edges[u].pb(v);
edges[v].pb(u);
costs[u].pb(w);
costs[v].pb(w);
}
num_of_vertices = n;
kilometers = k;
p(0,0,0,-1);
ans = mini;
if (ans == INF)
ans = -1;
return ans;
}
