#include "closing.h"
#include <iostream>
#include <vector>
#include <queue>
#include <array>
#define ll long long
using namespace std;
vector <ll> V, U;
vector <array<ll, 3>> T;
priority_queue <array<ll, 3>, vector<array<ll, 3>>, greater<array<ll, 3>>> pq;
bool B[200000];
bool done[200000];
ll dist[200000], P[200000];
vector <array<ll, 2>> adj[200000];
ll n, x, y, k, l, tot, tot2, f, mn, mnid;
bool dfs(ll u, ll p, ll w) {
if (u == y) {
U.push_back(w);
V.push_back(u);
B[u] = 1;
l = tot = w;
return 1;
}
for (auto [v, z] : adj[u]) {
if (v == p) continue;
auto ok = dfs(v, u, w+z);
if (ok) {
U.push_back(w);
V.push_back(u);
B[u] = 1;
tot += max(w, l-w);
tot2 += min(w, l-w);
return 1;
}
}
return 0;
}
void dfs2(ll u, ll p, ll w) {
for (auto [v, z] : adj[u]) {
if (v == p) continue;
P[v] = u;
dfs2(v, u, w+z);
}
}
void solve(ll u, ll p, ll w1, ll w2) {
if (!B[u]) {
T.push_back({2*w1, 2, u});
pq.push({2*w1, 2, u});
if (w1 <= w2-w1) {
pq.push({2*(w2-w1), 2, u});
T.push_back({2*(w2-w1), 2, u});
}
else {
pq.push({w2, 1, u});
T.push_back({w2, 1, u});
}
}
else if (abs(w1-(l-w1)) < mn) mn = abs(w1-(l-w1)), mnid = u;
for (auto [v, z] : adj[u]) {
if (v == p) continue;
if (B[u] && !B[v]) solve(v, u, min(w1, l-w1)+z, max(w1, l-w1)+z);
else solve(v, u, w1+z, w2+z);
}
}
void case1() {
while (!pq.empty()) pq.pop();
dfs(x, -1, 0);
solve(x, -1, 0, 0);
ll s = k, res = 0;
if (s >= tot) {
res = 2*(ll)V.size();
s -= tot;
vector <array<ll, 2> > tmp;
while (!pq.empty()) {
auto [w, t, u] = pq.top();
pq.pop();
//cout << s << " " << w << " " << t << " " << u << endl;
if (t == 2 && s >= w/2 && !done[u]) {
tmp.push_back({w/2, u});
s -= w/2, ++res;
}
else if (t == 1 && s >= w) {
s -= w, res += 2;
done[u] = 1;
}
else if (t == 1) {
for (int i=(ll)tmp.size()-1; i>=max(0LL, (ll)tmp.size()-3); --i) {
if (s+tmp[i][0] >= w && P[u] != tmp[i][1]) {
f = max(f, res+1);
}
}
}
}
}
f = max(f, res);
}
void case2() {
while (!pq.empty()) pq.pop();
ll s = k, res = 0;
pq.push({0, x, 0});
pq.push({0, y, 0});
dist[x] = dist[y] = 0;
while (!pq.empty()) {
auto [w, u, d] = pq.top();
pq.pop();
if (dist[u] != w) continue;
if (s >= w) s -= w, ++res;
for (auto [v, z] : adj[u]) {
if (dist[v] > dist[u]+z) {
dist[v] = dist[u]+z;
pq.push({dist[v], v, 0});
}
}
}
f = max(f, res);
}
void case3() {
P[mnid] = mnid;
dfs2(mnid, -1, 0);
while (!pq.empty()) pq.pop();
for (int i=0; i<n; ++i) done[i] = 0;
ll s = k, res = 0;
if (s >= tot2+mn) {
s -= tot2+mn;
res = (ll)V.size() + 1;
for (int i=0; i<V.size(); ++i) {
if (V[i] == mnid) continue;
pq.push({2*(max(U[i], l-U[i])-min(U[i], l-U[i])), 2, V[i]});
}
for (auto [x, y, z] : T) {
pq.push({x, y, z});
}
vector <array<ll, 2> > tmp;
while (!pq.empty()) {
auto [w, t, u] = pq.top();
pq.pop();
//cout << s << " " << w << " " << t << " " << u << endl;
if (t == 2 && s >= w/2 && !done[u]) {
tmp.push_back({w/2, u});
s -= w/2, ++res;
}
else if (t == 1 && s >= w) {
s -= w, res += 2;
done[u] = 1;
}
else if (t == 1) {
for (int i=(ll)tmp.size()-1; i>=max(0LL, (ll)tmp.size()-3); --i) {
if (s+tmp[i][0] >= w && P[u] != tmp[i][1]) {
f = max(f, res+1);
}
}
}
}
}
f = max(f, res);
}
int max_score(int N, int X, int Y, long long K,
std::vector<int> eu, std::vector<int> ev, std::vector<int> W)
{
for (int i=0; i<N; ++i) {
adj[i].clear();
dist[i] = 1e18;
B[i] = done[i] = 0;
}
T.clear();
V.clear();
U.clear();
while (!pq.empty()) pq.pop();
n = N, x = X, y = Y, k = K, f = -1e18, mn = 1e18, mnid = -1, tot2 = 0;
for (int i=0; i<N-1; ++i) {
adj[eu[i]].push_back({ev[i], W[i]});
adj[ev[i]].push_back({eu[i], W[i]});
}
case1();
case2();
case3();
return int(f);
}
