#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <vector>
#include <map>
typedef long long ll;
using namespace std;
vector<vector<pair<int, ll>>> adj;
vector<ll> a, b;
vector<map<ll, int>> dp;
void bfs(int st, vector<ll> &dist) {
queue<int> q;
q.push(st);
dist[st] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto &e : adj[u]) {
int v = e.first;
ll w = e.second;
if (dist[v] != -1) continue;
dist[v] = dist[u] + w;
q.push(v);
}
}
}
int solve(int i, ll rem, int n) {
if (i == n) return 0;
if (dp[i].count(rem)) return dp[i][rem];
int res = solve(i + 1, rem, n);
if (rem >= a[i]) res = max(res, 1 + solve(i + 1, rem - a[i], n));
if (rem >= b[i]) res = max(res, 2 + solve(i + 1, rem - b[i], n));
return dp[i][rem] = res;
}
int max_score(int n, int x, int y, ll K, vector<int> U, vector<int> V, vector<int> W) {
adj.assign(n, {});
for (int i = 0; i < n - 1; ++i) {
int u = U[i], v = V[i];
ll w = W[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
vector<ll> distX(n, -1), distY(n, -1);
bfs(x, distX);
bfs(y, distY);
a.resize(n, 1e18 + 3);
b.assign(n, 0);
for (int i = 0; i < n; ++i) {
a[i] = min(distX[i], distY[i]);
b[i] = max(distX[i], distY[i]);
}
dp.resize(n);
int score = solve(0, K, n);
return score;
}
