// Author: Kajetan Ramsza
#include "closing.h"
#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;
#ifdef DEBUG
auto& operator<<(auto &os, const pair<auto, auto> &p) {
return os<<"("<<p.first<<", "<<p.second<<")";
}
auto& operator<<(auto &os, const auto &v) {
os<<"{";
for(auto it=begin(v);it!=end(v);++it) {
if(it!=begin(v)) os<<", ";
os<<(*it);
}
return os<<"}";
}
void dbg_out(auto... x) {
((cerr<<' '<<x), ...) << endl;
}
#define dbg(x...) cerr<<"("<<#x<<"):", dbg_out(x);
#else
#define dbg(...)
#endif
const ll inf = ll(1e18) + 7;
int n, x, y;
ll K;
vector<vector<pair<int, ll>>> g;
vll dist_x, dist_y;
int solve() {
using T = tuple<ll, int, int>;
priority_queue<T, vector<T>, greater<T>> q;
vector<ll> closing(n, 0);
ll k = K;
int res = 2;
auto visited = [&](int v, int root) -> bool {
return closing[v] >= (root == x ? dist_x[v] : dist_y[v]);
};
auto add_new = [&](int v, int root) {
if(!visited(v, root)) return;
dbg(v, root);
for(auto [e, d] : g[v]) {
if(visited(e, root)) continue;
q.push({(root == x ? dist_x[e] : dist_y[e]) - closing[e], e, root});
}
};
add_new(x, x);
add_new(y, y);
while(!q.empty()) {
auto [cost, v, root] = q.top(); q.pop();
if(visited(v, root)) continue;
dbg(cost, v, root);
if(cost > k) return res;
k -= cost;
closing[v] = root == x ? dist_x[v] : dist_y[v];
res++;
add_new(v, root);
}
return res;
}
vll distance(int root) {
queue<int> q;
q.push(root);
vll dist(n, inf);
dist[root] = 0;
while(!q.empty()) {
int v = q.front(); q.pop();
for(auto [e, d] : g[v]) {
if(dist[e] < inf) continue;
dist[e] = dist[v] + d;
q.push(e);
}
}
return dist;
}
int max_score(int N, int X, int Y, ll _K,
vi U, vi V, vi W) {
n = N; x = X; y = Y; K = _K;
dbg(n, x, y, K);
g.resize(n);
rep(i,0,n-1) {
g[U[i]].emplace_back(V[i], W[i]);
g[V[i]].emplace_back(U[i], W[i]);
}
dist_x = distance(x);
dist_y = distance(y);
int result = solve();
g.clear();
dist_x.clear();
dist_y.clear();
return result;
}
