#include <bits/stdc++.h>
#define endl '\n'
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define fo(i,n) for(auto i =0 ; i < n;i++)
#define fore(i,l,r) for(auto i = l; i < r;i++)
#define forex(i,r,l) for(auto i = r; i >= l; i--)
#define ffo(i,n) forex(i,n-1,0)
#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define sz(x) (int)x.size()
#define gcd(a,b) __gcd(a,b)
#define vii vector<ii>
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>;using ii = pair<int,int>;using mii = map<int,int>;
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
const int LOG = 13;
struct fenwick{
vector<ll> ft;int n;
fenwick(int kkk){n=kkk;ft.resize(n+2,0);}
void update(int idx, ll val){for(; idx < n; idx += lsb(idx))ft[idx]+=val;}
ll query(int idx){ll res = 0;for(;idx>0;idx-=lsb(idx))res+=ft[idx];return res;}
ll query(int l, int r ){if(l>r)return 0;return query(r) - query(l-1);}
int lwb(ll v){
ll sum = 0;int pos=0;
for(int i=LOG; i>=0; i--)
if(pos + (1 << i) < n and sum + ft[pos + (1 << i)] < v){
sum += ft[pos + (1 << i)];pos += (1 << i);
}return pos + 1;
}
};
int max_score(int n, int x, int y, ll k, vector<int> u, vector<int> v, vector<int> w){
bool linea= 1;
fo(i,n-1)if(!(u[i] == i and v[i] == i+1))linea =0;
if(linea){
ll suf[n+1]{}, pre[n+1]{};
fore(i,1,n)pre[i] = (i ? w[i-1] : 0) + (i ? pre[i-1] : 0);
ffo(i,n-1)suf[i] = w[i] + suf[i+1];
ll disx[n+1]{};
for(int i = x-1; i >= 0; i--)disx[i] = disx[i+1] + w[i];
ll disy[n+1]{} , ans = 0;
for(int i = y+1; i <= n-1;i++)disy[i] = disy[i-1] + w[i-1];
int tot = 0;
vi ord;fo(i,x+1)ord.pb(disx[i]);fore(i,y,n)ord.pb(disy[i]);
sort(all(ord)) ;
for(int j = x; j <= n-1; j++ ){
map<int, int> indices;
fo(i, sz(ord))indices[ord[i]]=0;
ans+= pre[j] - pre[x];
fenwick cnt(2*n+1), sum(2*n+1);
for(int l=y;l>=0;l--){
if(l>j)ans+=suf[l]- suf[y];
else{
if(l>x){
if(j>=l){
if(suf[l]-suf[y] > pre[l] - pre[x]){
ans -= pre[l] - pre[x];
ans+=suf[l]-suf[y];
}
}
else ans+= suf[l]-suf[y];
}
else{ans+=suf[l]-suf[y];if(l>=j)ans-=suf[l] - suf[x];}
}
}
for(int i = max(y+1,j+1); i <= n-1; i++){
int pos = lower_bound(all(ord), disy[i])-ord.begin() ,pos2 = pos;
pos+=indices[ord[pos]];indices[ord[pos2]]++;
cnt.update(pos+1, +1);
sum.update(pos+1, +disy[i]);
}
for(int l =0;l<=y;l++){
if(ans <= k){
int rb = sum.lwb(k-ans+1) - 1;
rb = cnt.query(1, rb);
tot = max(tot, j-x+1 + y-l+1 + rb + max(j-y, 0) + max(x-l, 0));
}
if(l>j)ans-=suf[l]- suf[y];
else{
if(l>x){
if(j>=l){
if(suf[l]-suf[y] > pre[l] - pre[x]){
ans += pre[l] - pre[x];
ans -=suf[l]-suf[y];
}
}
else ans -= suf[l]-suf[y];
}
else{ans-=suf[l]-suf[y];if(l>=j)ans+=suf[l] - suf[x];}
}
int pos = lower_bound(all(ord), disx[l])-ord.begin(),pos2=pos;
if(l <= x-1){
pos+=indices[ord[pos]];indices[ord[pos2]]++;
cnt.update(pos+1, +1);
sum.update(pos+1, +disx[l]);
}
}
}
return tot;
}
vector<vector<pair<ll,ll>>>graph(n+2);
fo(i,n-1){graph[u[i]].pb({v[i], w[i]}), graph[v[i]].pb({u[i], w[i]});}
// cout << "llegue" << endl ;return 1;
priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
pq.push({0, x});pq.push({0,y});
vi vis(n+1, 0);vis[x]=1; vis[y]=1;
int ans = 0;ll sumact =0;
while(sz(pq)){
auto tp = pq.top();pq.pop();
// cout << tp.f << " " << tp.s << endl;
if(tp.f + sumact > k)return ans;
sumact+=tp.f;
ans++;
for(auto [neigh, cost] : graph[tp.s]){
if(!vis[neigh])pq.push({tp.f + cost, neigh}), vis[neigh] = 1;
}
}
return ans;
}
