#include "closing.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/home/ioi/egoi2024/d2/debug.h"
#else
#define debug(...) void(37)
#endif
template<typename T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;
int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
vector<vector<array<int, 2>>> g(N);
for (int i = 0; i < N - 1; ++i) {
g[U[i]].push_back({V[i], W[i]});
g[V[i]].push_back({U[i], W[i]});
}
constexpr int64_t inf = int64_t(1E16);
auto Sp = [&](int source) {
vector<int64_t> dist(N, inf);
min_pq<pair<int64_t, int>> pq;
auto Add = [&](int v, int64_t d) {
if (dist[v] > d) {
dist[v] = d;
pq.emplace(d, v);
}
};
Add(source, 0);
while (!pq.empty()) {
auto[d, v] = pq.top(); pq.pop();
if (dist[v] < d) continue;
for (auto[u, w] : g[v]) {
Add(u, d + w);
}
}
return dist;
};
auto dx = Sp(X);
auto dy = Sp(Y);
int ans = 0;
{ //disjoint case
auto all = dx;
all.insert(all.end(), dy.begin(), dy.end());
sort(all.begin(), all.end());
int64_t tot = 0;
for (auto x : all) {
tot += x;
if (tot <= K) ans++;
}
}
map<int64_t, vector<int64_t>> groups;
for (int i = 0; i < N; ++i) {
groups[dx[i] - dy[i]].push_back(min(dx[i], dy[i]));
}
if (dx[Y] > 2 * K) return ans;
vector<array<int64_t, 2>> picks;
int taken = 0;
for (auto[x, v] : groups) {
int64_t cost = abs(x);
sort(v.begin(), v.end());
debug(v);
K -= v[0];
taken++;
picks.push_back({cost, -1});
for (int i = 1; i < int(v.size()); ++i) {
if (v[i] >= cost) {
picks.push_back({v[i], cost});
} else {
picks.push_back({v[i], -1});
picks.push_back({cost, -1});
}
}
}
debug(groups, picks);
int s = int(picks.size());
auto Cost = [&](array<int64_t, 2> x) -> int64_t {
if (x[1] == -1) return x[0] * 2;
return (x[0] + x[1]);
};
sort(picks.begin(), picks.end(), [&](array<int64_t, 2> x, array<int64_t, 2> y) {
return Cost(x) < Cost(y);
});
vector<int> first_one(s + 1, -1), last_one(s + 1, -1);
for (int i = s - 1; i >= 0; --i) {
first_one[i] = first_one[i + 1];
if (picks[i][1] == -1) first_one[i] = i;
}
for (int i = 0; i < s; ++i) {
last_one[i] = last_one[i - !!i];
if (picks[i][1] == -1) last_one[i] = i;
}
vector<int64_t> pref(s + 1), ct(s + 1);
for (int i = 0; i < s; ++i) {
pref[i + 1] = pref[i] + picks[i][0] + max<int64_t>(picks[i][1], 0);
ct[i + 1] = ct[i] + 1 + (picks[i][1] != -1);
}
debug(picks);
debug(first_one);
debug(pref, ct);
auto Apply_best = [&](int rem, int64_t start) {
int64_t left = K - start;
int res = taken + (rem != -1);
if (left < 0) return;
int fp = int(lower_bound(pref.begin(), pref.begin() + 1 + rem, left + 1) - pref.begin()) - 1;
if (fp != -1) {
res += ct[fp];
left -= pref[fp];
}
if (fp == rem && rem != s - 1) {
int bp = int(lower_bound(pref.begin() + 1 + rem, pref.end(), left + pref[rem + 1] + 1) - pref.begin()) - 1;
res += ct[bp] - ct[rem + 1];
left -= pref[bp] - pref[rem + 1];
if (first_one[bp] != -1 && picks[first_one[bp]][0] <= left) res++;
else if (bp < s && picks[bp][1] != -1 && last_one[bp] != -1 && picks[last_one[bp]][0] + left >= picks[bp][0] + picks[bp][1]) res++;
} else {
if (first_one[fp] != -1 && picks[first_one[fp]][0] <= left) res++;
else if (picks[fp][1] != -1 && last_one[fp] != -1 && picks[last_one[fp]][0] + left >= picks[fp][0] + picks[fp][1]) res++;
}
debug(rem, res);
ans = max(ans, res);
};
Apply_best(-1, 0);
for (int i = 0; i < s; ++i) {
if (picks[i][1] != -1) {
Apply_best(i, picks[i][0]);
}
}
return ans;
}
