#include "closing.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, x, y; ll k;
const int MAXN = 2e5 + 25;
vector <pair <ll, ll>> adj[MAXN];
ll dist[MAXN][2], f[MAXN], g[MAXN];
vector <int> cur, path;
void add_edge (int x, int y, int z) {
adj[x].push_back({y, z});
adj[y].push_back({x, z});
}
void dfs (int pos, int par, ll d, int c) {
dist[pos][c] = d;
for (auto j : adj[pos]) {
if (j.first != par) {
dfs(j.first, pos, d + j.second, c);
}
}
}
bool dfs2 (int pos, int par, int c) {
cur.push_back(pos);
if (pos == c) {
path = cur;
return 1;
}
for (auto j : adj[pos]) {
if (j.first != par) {
if (dfs2(j.first, pos, c)) {
return 1;
}
}
}
cur.pop_back();
return 0;
}
int solve1 () {
vector <ll> zz;
for (int i = 1; i <= n; i++) {
zz.push_back(f[i]);
zz.push_back(g[i]);
}
sort(zz.begin(), zz.end());
for (int i = 1; i < 2 * n; i++) zz[i] += zz[i - 1];
int ans1 = upper_bound(zz.begin(), zz.end(), k) - zz.begin();
return ans1;
}
struct OfflineBit {
vector <ll> tree, comp;
void insert (ll x) {
comp.push_back(x);
}
void build () {
sort(comp.begin(), comp.end());
comp.resize(unique(comp.begin(), comp.end()) - comp.begin());
tree.resize(comp.size());
tree.insert(tree.begin(), 0);
}
int find (ll x) {
return upper_bound(comp.begin(), comp.end(), x) - comp.begin();
}
inline int lsb (int x) {
return x & (-x);
}
void add (ll x, ll y) {
x = find(x);
assert(x >= 0 && x < (int)(tree.size()));
for (; x < int(tree.size()); x += lsb(x)) {
tree[x] += y;
}
}
ll get (ll x) {
x = find(x);
assert(x >= 0 && x < (int)(tree.size()));
ll ret = 0;
for (; x > 0; x -= lsb(x)) {
ret += tree[x];
}
return ret;
}
};
int solve2 () {
ll u = k;
for (auto j : path) {
u -= f[j];
f[j] = g[j] - f[j];
g[j] = 1e18;
}
if (u < 0) {
return -1;
}
vector <pair <ll, ll>> a;
for (int i = 1; i <= n; i++) {
a.push_back({g[i], f[i]});
}
sort(a.begin(), a.end());
OfflineBit c1, c2;
ll cur_sum = 0;
c1.insert(0); c2.insert(0);
for (auto i : a) {
cur_sum += i.second;
c1.insert(i.second); c1.insert(i.first - i.second);
c2.insert(i.second); c2.insert(i.first - i.second);
c1.insert(cur_sum); c2.insert(cur_sum);
}
c1.build(); c2.build();
cur_sum = 0;
for (auto i : a) {
c1.add(i.second, 1); c2.add(i.second, i.second);
}
int ret = -1e9;
auto val = [&] (int cnt) -> int {
if (cur_sum > u) return -1e9;
ll l = 0, r = 1e18, ans = -1;
while (l <= r) {
ll mid = (l + r) / 2;
if (c2.get(mid) <= u - cur_sum) {
l = mid + 1; ans = mid;
} else {
r = mid - 1;
}
}
if (ans == -1) return -1e9;
ll v = c1.get(ans + 1) - c1.get(ans);
ll r2 = (u - cur_sum - c2.get(ans)) / (ans + 1);
r2 = min(r2, v);
return r2 + c1.get(ans) + cnt;
};
ret = val(0);
int ee = 0;
for (auto i : a) {
ee++; cur_sum += i.second;
c1.add(i.second, -1); c2.add(i.second, -i.second);
c1.add(i.first - i.second, 1); c2.add(i.first - i.second, i.first - i.second);
ret = max(ret, val(ee));
}
return ret + (int)path.size();
}
int max_score (int N2, int X2, int Y2, ll K2, vector <int> u, vector <int> v, vector <int> w) {
n = N2; x = X2; y = Y2; k = K2;
x++; y++;
cur.clear(); path.clear();
for (int i = 1; i <= n; i++) {
adj[i].clear();
}
for (int i = 0; i + 1 < n; i++) {
add_edge(u[i] + 1, v[i] + 1, w[i]);
}
dfs(x, -1, 0, 0);
dfs(y, -1, 0, 1);
dfs2(x, -1, y);
for (int i = 1; i <= n; i++) {
f[i] = min(dist[i][0], dist[i][1]);
g[i] = max(dist[i][0], dist[i][1]);
}
int ret1 = solve1(), ret2 = solve2();
return max(ret1, ret2);
}
