#include<bits/stdc++.h> using namespace std; const int N=2e5+3; const int inf = 1e9+7; #define ll long long #define fi first #define se second #define VOI void map<ll,int>best[N]; int ans = inf; int n,k; vector<pair<int,ll>>adj[N]; VOI DFS(int u,int pre){ best[u][0] = 0; for(pair<int,ll> tmp : adj[u]){ int v = tmp.fi; ll weight = tmp.se; if(v == pre)continue; DFS(v,u); if(best[v].size() > best[u].size())swap(best[v],best[u]); for(auto [len,paths] : best[v]){ ll newlen = k - weight - len; if(newlen < 0)continue; if(best[u].find(newlen) != best[u].end()){ ans = min(ans,paths + 1 + best[u][newlen]); } } for(auto [len,paths] : best[v]){ if(best[u].find(len + weight) == best[u].end()) best[u][len+weight] = inf; best[u][len + weight] = min(best[u][len + weight],paths + 1); } best[v].clear(); } } /* === HÀM IOI – CHỈ THAY PHẦN ĐỌC INPUT / OUTPUT === */ int best_path(int _n, int _k, int H[][2], int L[]) { n = _n; k = _k; ans = inf; for(int i=0;i<n;i++){ adj[i].clear(); best[i].clear(); } for(int i=0;i<n-1;i++){ int x = H[i][0]; int y = H[i][1]; ll w = L[i]; adj[x].push_back({y,w}); adj[y].push_back({x,w}); } DFS(0,-1); if(ans == inf) return -1; return ans; }