#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define all(v) v.begin(), v.end()
#define f first
#define s second
using namespace std;
namespace lol
{
const int maxn=2e5+100;
int n, x, y, onp[maxn];
ll k;
ll dist[maxn][2], a[maxn], b[maxn];
vector <pair <int, int> > edge[maxn];
vector <int> path;
void dfs(int v, int pred, int t) {
for(auto [to, w] : edge[v]) {
if(to == pred) continue;
dist[to][t] = dist[v][t] + w;
dfs(to, v, t);
}
}
int dfs2(int v, int pred = -1) {
path.pb(v);
onp[v] = 1;
if(v == y) return 1;
for(auto [to, w] : edge[v]) {
if(to == pred) continue;
if(dfs2(to, v)) return 1;
}
onp[v] = 0;
path.pop_back();
return 0;
}
int noCommon() {
multiset <ll> st;
for(int i = 1; i <= n; ++i) {
st.insert(a[i]);
}
ll K = k;
int ans = 0;
while(st.size()) {
ll s = *st.begin();
st.erase(st.begin());
if(K < s) {
break;
}
K -= s;
ans++;
}
return ans;
}
int solve(int N, int X, int Y, long long K2, vector<int> U, vector<int> V, vector<int> W) {
n = N;
x = X + 1;
y = Y + 1;
k = K2;
for(int i = 1; i <= n; ++i) {
edge[i].clear();
onp[i] = 0;
}
for(int i = 0; i < n - 1; ++i) {
int l = U[i] + 1;
int r = V[i] + 1;
int w = W[i];
edge[l].pb({r, w});
edge[r].pb({l, w});
}
dist[x][0] = 0;
dist[y][1] = 0;
dfs(x, -1, 0);
dfs(y, -1, 1);
for(int i = 1; i <= n; ++i) {
a[i] = min(dist[i][0], dist[i][1]);
b[i] = max(dist[i][0], dist[i][1]) - a[i];
}
path.clear();
vector <pair <ll, int> > vec2;
multiset <pair <ll, int> > st;
dfs2(x);
for(int i = 1; i <= n; ++i) {
if(a[i] > b[i] && onp[i] == 0) {
vec2.pb({a[i] + b[i], i});
}
st.insert({a[i], i});
}
sort(all(vec2));
ll K = k;
for(auto i : path) {
K -= a[i];
st.erase({a[i], i});
st.insert({b[i], -i});
}
int res = noCommon();
for(int i = 0; i <= (int)vec2.size(); ++i) {
multiset <pair <ll, int> > temp = st;
int ans = i * 2 + path.size();
while(temp.size()) {
ll s = temp.begin()->f;
int v = temp.begin()->s;
temp.erase(temp.begin());
if(K < s) {
break;
}
K -= s;
ans++;
if(v > 0) {
temp.insert({b[v], -v});
}
}
res = max(res, ans);
if(i == (int)vec2.size()) break;
// cout << " " << i << " " << ans << " " << vec2[i].f << " " << vec2[i].s << endl;
if(K < vec2[i].f)
break;
K -= vec2[i].f;
int v = vec2[i].s;
st.erase({a[v], v});
st.erase({b[v], -v});
}
return res;
};
}
int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W) {
return lol::solve(N, X, Y, K, U, V, W);
}
