#include "race.h"
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define sz(a) (int)a.size()
const int N = 2e5 + 10;
vector<pair<int, ll>> adj[N];
bool vis[N];
int s[N];
int K;
map<ll, int> dp;
void recalc(int u, int par){
s[u] = 1;
for(auto x: adj[u]){
int v = x.first;
if(v == par || vis[v])continue;
recalc(v, u);
s[u] += s[v];
}
}
int find_centroid(int u, int need, int par){
for(auto x: adj[u]){
int v = x.first;
if(v == par || vis[v])continue;
if(s[v] > need)return find_centroid(v, need, u);
}
return u;
}
int ans = INT_MAX;
void dfs(int u, int par, ll weight, int type, int depth){
if(weight > K)return;
if(type == 0){
if(dp.count(K - weight)){
ans = min(ans, dp[K - weight] + depth);
}
}
else{
if(!dp.count(weight))dp[weight] = depth;
else dp[weight] = min(dp[weight], depth);
}
for(auto x: adj[u]){
ll v = x.first, w = x.second;
if(v == par || vis[v])continue;
dfs(v, u, weight + w, type, depth + 1);
}
}
void centroid_decomp(int u){
recalc(u, -1);
int c = find_centroid(u, s[u] / 2, -1);
vis[c] = true;
dp.clear();
dp[0] = 0;
for(auto x: adj[c]){
ll v = x.first, w = x.second;
if(vis[v])continue;
dfs(v, -1, w, 0, 1);
dfs(v, -1, w, 1, 1);
}
for(auto x: adj[c]){
int v = x.first;
if(vis[v])continue;
centroid_decomp(v);
}
}
int best_path(int n, int k, int h[][2],int l[]){
ans = INT_MAX;
K = k;
for(int i = 0;i < n; ++i){
adj[i].clear();
vis[i] = 0;
s[i] = 0;
}
dp.clear();
for(int i = 0;i < n - 1; ++i){
adj[h[i][0]].pb({h[i][1], l[i]});
adj[h[i][1]].pb({h[i][0], l[i]});
}
centroid_decomp(0);
if(ans == INT_MAX)return -1;
return ans;
}
/*
void solve()
{
int n, k;
cin >> n >> k;
K = k;
vector<vector<int>> h(n - 1, vector<int>(2, 0));
vector<int> l(n - 1);
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) << "\n";
}
int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;
//cin >> t;
while(t--)
{
solve();
}
}
*/
