#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, t[8*maxn], t2[8*maxn];
ll dist[maxn][2], a[maxn], b[maxn];
vector <pair <ll, int> > vec;
vector <pair <int, int> > edge[maxn];
vector <int> path;
void build(int v, int tl, int tr) {
if(tl == tr) {
t[v] = vec[tl-1].f;
t2[v] = 1;
return;
}
build(v * 2, tl, (tl + tr) / 2);
build(v * 2 + 1, (tl + tr) / 2 + 1, tr);
t[v] = t[v * 2] + t[v * 2 + 1];
t2[v] = t2[v * 2] + t2[v * 2 + 1];
}
void upd(int v, int tl, int tr, int pos) {
if(pos < tl || tr < pos) return;
if(tl == tr) {
t[v] = 0;
t2[v] = 0;
return;
}
upd(v * 2, tl, (tl + tr) / 2, pos);
upd(v * 2 + 1, (tl + tr) / 2 + 1, tr, pos);
t[v] = t[v * 2] + t[v * 2 + 1];
t2[v] = t2[v * 2] + t2[v * 2 + 1];
}
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 get(int v, int tl, int tr, ll K) {
if(tl == tr) {
if(t[v] <= K) return t2[v];
return 0;
}
if(t[v] <= K) return t2[v];
if(t[v * 2] <= K) return t2[v * 2] + get(v * 2 + 1, (tl + tr) / 2 + 1, tr, K - t[v * 2]);
return get(v * 2, tl, (tl + tr) / 2, K);
}
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);
vec.clear();
for(int i = 1; i <= n; ++i) {
if(a[i] > b[i] && onp[i] == 0) {
vec2.pb({a[i] + b[i], i});
}
if(onp[i] == 1) {
vec.pb({b[i], -i});
}
else {
if(a[i] <= b[i]) {
vec.pb({a[i], i});
vec.pb({b[i], -i});
}
else {
vec.pb({a[i], i});
}
}
}
sort(all(vec2));
sort(all(vec));
int m = (int)vec.size();
build(1, 1, m);
ll K = k;
for(auto i : path) {
K -= a[i];
}
int res = noCommon();
if(K < 0) return res;
for(int i = 0; i <= (int)vec2.size(); ++i) {
multiset <pair <ll, int> > temp = st;
int ans = i * 2 + path.size() + get(1, 1, m, K);
// cout << " " << i << " " << ans << endl;
res = max(res, ans);
if(i == (int)vec2.size()) break;
if(K < vec2[i].f)
break;
K -= vec2[i].f;
int v = vec2[i].s;
int fi = lower_bound(all(vec), make_pair(a[v], v)) - vec.begin() + 1;
upd(1, 1, m, fi);
}
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);
}
