#include <bits/stdc++.h>
using int64 = long long;
int max_score(int n, int a, int b, long long k, std::vector<int> u, std::vector<int> v, std::vector<int> w) {
std::vector<std::vector<std::pair<int, int64>>> adj(n);
for (int i = 0; i < n - 1; ++i) {
adj[u[i]].push_back({v[i], w[i]});
adj[v[i]].push_back({u[i], w[i]});
}
int64 inf = 1e15;
auto dijkstra = [&](int u) {
std::vector<int64> dist(n, inf);
std::priority_queue<std::pair<int, int>> pq;
dist[u] = 0;
pq.push({-dist[u], u});
std::vector<bool> vis(n);
vis[u] = true;
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
d = -d;
for (auto &[i, w] : adj[u]) {
if (vis[i] or dist[i] <= d + w) {
continue;
}
dist[i] = d + w;
vis[i] = true;
pq.push({-dist[i], i});
}
}
return dist;
};
auto da = dijkstra(a), db = dijkstra(b);
std::vector<int> na(n), nb(n);
std::iota(na.begin(), na.end(), 0);
std::iota(nb.begin(), nb.end(), 0);
std::sort(na.begin(), na.end(), [&](int i, int j) {
return da[i] < da[j];
});
std::sort(nb.begin(), nb.end(), [&](int i, int j) {
return db[i] < db[j];
});
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
int64 used = 0;
std::vector<int64> c(n);
for (int _ = 0; _ < i; ++_) {
used += std::max(0LL, da[na[_]] - c[na[_]]);
c[na[_]] = std::max(c[na[_]], da[na[_]]);
}
for (int _ = 0; _ < j; ++_) {
used += std::max(0LL, db[nb[_]] - c[nb[_]]);
c[nb[_]] = std::max(c[nb[_]], db[nb[_]]);
}
if (used <= k) {
ans = std::max(ans, i + j);
}
}
}
return ans;
}
